JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (December - 2017 - R15)

Define Transition diagram.

Explain about ε-closure().

Write a short note on Derivation Tree.

Explain Rightmost Derivation with an example.

Define Chomsky Normal Form.

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

Write a short note on Church’s hypothesis.

Write a short note on Recursively Enumerable languages.

Write about decidability of problems.

Define NP-complete problems.

Convert the Moore machine to determine residue mod 3 into Mealy machine.

Construct the minimum state automata for the following.

Convert the following NFA with ε to equivalent DFA.

Design NFA accepting string with a’s and b’s such that string containing two consecutive a’s or two consecutive b’s.

For the following grammar give the leftmost and rightmost derivation for the string ‘00101’. S → A1B, A → 0A / ε, B → 0B / 1B / ε

Prove that the following language {aⁿbⁿ | n ≥ 1} is not a regular.

Write a R.E. for the following DFA.

Construct the right linear grammar for the language (0+1)*00(0+1)*.

Convert the following grammar to Greibach Normal Form: S→ABA | AB | BA | AA | B, A→aA | a, B→bB | b

Convert the following Context Free Grammar into Chomsky Normal Form: S→aaaaS | aaaa

Reduce the following grammar such that there are no UNIT productions: S → AA, A → B | BB, B → abB | b | bb

Construct CFG for the PDA M = ({q0,q1}, {0,1}, {R,Z0}, δ, q0, Z0, Φ).

Design a TM to recognize the language L= {0ⁿ1ⁿ0ⁿ | n ≥ 1}.

Design TM which will recognize strings containing equal number of a's and b's.

Design a TM to accept the language L= {w c w^R | w ε (a+b)*}.

Design a TM to recognize all strings consisting of odd number of 1's.

Give the closure properties of deterministic context free languages.

What are undecidable problems? Give example.

Give definitions of P and NP problems.

Explain TM halting problem.