Download AKTU B-Tech 4th Sem 2018-19 RCS403 Theory Of Automata And Formal Languages Question Paper

Firstranker's choice

FirstRanker.com

Printed Pages: 02

--- Content provided by‌ FirstRanker.com ---

Paper Id: 110257 Roll No. Sub Code: RCS403

B TECH

(SEM-IV) THEORY EXAMINATION 2018-19

THEORY OF AUTOMATA AND FORMAL LANGUAGES

Time: 3 Hours Total Marks: 70

--- Content provided by‌ FirstRanker.com ---

Note: Attempt all Sections. If require any missing data; then choose suitably.

SECTION A

1. Attempt all questions in brief. 2 x 7 = 14
   1. For the given language L1 = e, L2 = {a}, L3 = Ø. Compute L1 L2* U L3*.
   2. Design a FA to accept the string that always ends with 101.
   3. Write regular expression for set of all strings such that number of a's divisible by 3 over ? = {a,b}

   --- Content provided by‍ FirstRanker.com ---

   4. Construct the CFG for the Language L = {a^2mbⁿ |n>=3}.
   5. What do you mean by ?-Closure in FA?
   6. Explain Universal TM.
   7. Explain Two Stack PDA.

--- Content provided by‌ FirstRanker.com ---

SECTION B

2. Attempt any three of the following: 7 x 3 = 21
   1. Construct a minimum state DFA from given FA
      
      Fig. 1
   2. Find the regular expression corresponding to the finite automata given below:
      

      --- Content provided by‌ FirstRanker.com ---

      
      Fig. 2
   3. Convert the following CFG to its equivalent GNF:
      S ? AA | a, A ? SS | b.
   4. Design a PDA for the following language:
      

      --- Content provided by FirstRanker.com ---

      L = {aⁱb^jc^k | i = j or j = k}
   5. Design a TM for the following language:
      L = { aⁿ⁺²bⁿ | n >0 }

SECTION C

--- Content provided by‌ FirstRanker.com ---

3. Attempt any one part of the following: 7x1=7
   1. Design FA for ternary number divisible by 5.
   2. Explain Myhill-Nerode Theorem using suitable example.
4. Attempt any one part of the following: 7 x1=7
   1. Prove that the following Language L = {aⁿbⁿ} is not regular
   2. Explain the Closure properties of regular expression.

   --- Content provided by⁠ FirstRanker.com ---

5. Attempt any one part of the following: 7x1=7
   1. Design the CFG for the following language:
      1. L = {0^m1ⁿ| m ? n & m,n = 1}
      2. L = {a^lb^mcⁿ | l + m = n & l,m > 1}
   2. Prove that the following Language L = {aⁿbⁿcⁿ} is not Context Free.

   --- Content provided by⁠ FirstRanker.com ---

6. Attempt any one part of the following: 7
   1. Design a PDA for the Language L
      Generate CFG for the given PDA M is defined as
   2. M = ({q0, q1}, {0,1} {x, zo}, 8,
      8 (q0,1, zo) = (q0, xzo)
      

      --- Content provided by​ FirstRanker.com ---

      8 (q0,1, x) = (q0, xx)
      8 (q0,0, x) = (q0, x)
      d (q0, e, x) = (q1, e)
      d (q1, e, x) = (q1, e)
      8 (q1,0, x) = (q1, xx)
      

      --- Content provided by⁠ FirstRanker.com ---

      8 (q1,0, zo) = ( q1, e)
      zo,
      where 8 is given
      ollows:

--- Content provided by⁠ FirstRanker.com ---

7. Attempt any one part of the following: 7x1=7
   1. Design a TM for the following,
      L = { aⁿbⁿcⁿ | n= 1}
   2. Write short note on:
      1. Recursive Language and Recursively Enumerable Language.
      2. PCP problem and Modified PCP Problem

   --- Content provided by‌ FirstRanker.com ---