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

Attempt all questions in brief. 2 x 7 = 14

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

1. Define alphabet, string and language.
2. Design a regular expression that accepts all the strings for input alphabet {a,b} containing exactly 2 a's.
3. Design a NFA that accepts all the strings for input alphabet {a,b} containing the substring abba.
4. Define Chomsky hierarchy.
5. Is context free language closed under union? If yes, give an example.

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

6. Convert NFA into equivalent DFA by taking any suitable example.
7. Remove useless productions from the given productions: S?AB|ab, A?aA|B|a, B?D|E

Attempt any three of the following: 7 x 3 = 21

1. Define Deterministic Finite Automata (DFA) and design a DFA that accepts the binary number whose equivalent is divisible by 5.

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

2. State recursive definition of regular expression and construct regularexpression corresponding to the state transition diagram as shown in Fig.1
   
3. Reduce the given grammar G=({S,A,B},{a,b},P,S) to Chomsky Normal Form. Where P is defined as:
   S? bA | aB
   A? bAA | aS | a
   

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

   B? aBB | bS | b
4. What is Push Down Automata (PDA)? Design the PDA for the language L = {wcw^R w? {a,b}*}
5. Define Turing Machine (TM). Construct the TM for the language L = {aⁿbⁿ | n>0}.

Attempt any one part of the following: 7x1=7

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

1. Describe Mealy and Moore machines with example. Convert the given Mealy machine as shown in Fig. 2 into Moore Machine.
   
2. Construct the minimum state automata equivalent to DFA described by Fig. 3
   

Attempt any one part of the following: 7x1=7

1. State Pumping Lemma for regular sets. Show that the set L= {a^p | p is a prime} is not regular.
2. Discuss closure properties i.e. concatenation, union, intersection, complement of regular languages.

Attempt any one part of the following: 7x1=7

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

1. Discuss inherent ambiguity of context free languages with suitable example. Construct the context free grammar that accepts language L={aⁱb^jc^k| i = j or j = k; i, j, k are positive integers}.
2. Define parse tree. Find parse tree for the string abbcde considering the productions-
   S?aAcBe
   A?Ab
   A?b
   

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

   B?d
   Is this ambiguous? Justify.

Attempt any one part of the following: 7x1=7

1. Differentiate between deterministic PDA (DPDA) and non-deterministic PDA (NPDA) with suitable example. Also discuss two stack PDA with example.

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

2. Construct a PDA equivalent to the following CFG productions:
   S?aAA, A?aS | bS|a

Attempt any one part of the following: 7x1=7

1. Write short notes on the following:
   1. Halting problem of Turing machine

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

   2. Recursive Language
   3. Variants of Turing Machine
2. Define Post's Correspondence Problem (PCP) and Modified PCP with its applications. Find any three PCP solutions of the lists x=(b,bab³,ba) and y=(b³,ba,a).