JNTU B.Tech II Year FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (December - 2018 - R15)

Define DFA.

Design FA which accepts set of all strings ending with 00.

Define Left linear Grammar.

Give the regular expression for the language all string over alphabet {0,1} containing at least two 0’s.

What is ambiguity in CFG?

Write the context free grammar for the language L={aⁿb²ⁿ/n≥1}

Give Instantaneous description ID of Turing Machine.

Define Type 0 Grammar.

List any 2 NP Hard Problems.

Define Turing reducibility.

Convert the following NFA with € - moves to DFA shown in figure 1.

Minimize the following DFA shown in figure 2.

Check whether the following two Finite Automaton’s are equivalent or not?

Finite Automaton (FA) 1 (figure 3):

Finite Automaton (FA) 2(figure 4):

Convert the following NFA with € moves to DFA in figure 5.

01[((10)*+111)*+0]*1

((01+10)*00)*

Find the regular grammar for the following Finite Automate shown in figure 6.

Construct FA for the following regular expressions (0+1)*(1+00)(0+1)*.

Convert the following grammar to Chomsky Normal Form

S→ ABA

A→ aA | ε

B→ bB | ε

and simplify the grammar

Write and explain closure properties of Context Free Languages.

State the Pumping Lemma for Context Free Languages.

Design Push down Automata for the language L = {aⁿb²ⁿ | n≥1}.

Design Turing Machine for the Language L={ aⁿbⁿcⁿ /n≥1 }

List the Closure properties of recursive Languages.

Design Turing Machine to compute the function n!

Design TM for performing proper subtraction of two numbers.

Briefly write about Universal Turning Machine (UTM).

What do you mean by NP Complete? List any 6 NP Complete Problems.

Discuss about turing Reducibility.

Write about:

1. Post Correspondence Problem
2. Halting problem of TM.