JNTU B.Tech II FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (May - 2019 - R13)

Define DFA and NFA.

Design NFA to accept set of all strings over {0,1} does not contain 3 consecutive zeros.

Define Left Linear Grammar.

Define Pumping Lemma for Regular sets.

Define UNIT Production.

What is reachable variable? Give an example.

Give instantaneous description ID of Turing Machine.

What is a Turing Machine?

Give any two examples of Decidable Problems.

Define NP hard problems.

Minimizing the following DFA as shown in figure 1.

Define Mealy and Moore Machines.

Convert the following NFA with € - moves to DFA as shown in Figure 2.

Design DFA for the language all strings over {0,1} which are ending with 00.

Show that the language L={ aⁿbⁿ / n≥1 } is not a Regular language.

Find the Regular Grammar equivalent to the following Finite Automata shown in figure 3.

Construct Right Linear Grammar and Left Linear Grammar for the Regular Expression 0*(11)* + 1001*

Give the RE for (i) All strings over {a,b} which contains even number of a's (ii) All strings over {a,b} which contains at least two a's (iii) All strings over {a,b} which contains at most two a's (iv) All strings over {a,b} which contains exactly two a's.

Minimize the following Context Free Grammar G=({S,A,B,C}, {a,b,c,d},P,S), where P is given as follows S→AC | SB, A→ bASC | a, B→ aSB | bbB, C→ Bc | ad

Design PDA for the language L={a²ⁿbⁿc⁴ /n≥1}.

Convert the following Context Free Grammar (CFG) to Chomskey Normal Form (CNF): S→AaB | aaB, A→€, B→bbA | €

Design PDA for the language L={aⁿb^n+mc^m | n,m≥1}.

Explain different types of Turing Machine.

Design TM for performing proper subtraction of two numbers.

Church’s hypothesis.

Counter machine.

Discuss about turing reducibility.

What is post correspondence problem? Verify whether the following PCP has solution or not? A={ba,ab,a,baa,b}, B={bab,baa,ba,a,aba}