Formal Languages and Automata Theory Important Questions

11 Feb 2016    07:59 pm

Unit-1

1. Define language over an alphabet with examples.

Write a DFA to accept set of all strings ending with 010.

2. Give example for Minimize the DFA . Understand 2

3. Construct a Moore machine to accept the following language.

L = { w |w mod 3 = 0} on ∑ = { 0,1,2}

4. Write any four differences between DFA and NFA Apply 2

5. Convert NFA with Ɛ to NFA with an example. Understand 2

6. Construct NFA for (0 + 1)*(00 + 11)(0 + 1)* and Convert to DFA. Apply 2

JNTU World www.alljntuworld.in JNTU World Downloaded From JNTU World (http://www.alljntuworld.in)

S. No. Questions Blooms

7. Construct NFA for (0 +1)*(00 + 11)(0 + 1)* and Draw the transition

table and transition diagram and example strings.

8. Illustrate given 2 FA‘s are equivalent or not with an example. Apply 6

9. Construct Mealy machine for (0 + 1)*(00 + 11) and convert to Moore

machine.

10. Convert Moore machine to Mealy machine with an example.

Unit-2

1. Convert Regular Expression 01* + 1 to Finite Automata.

2. Convert given Finite Automat to Regular Expression using Arden’s

theorem.

3. Convert given Finite Automat to Regular Expression using standard

method(Rij

4. Explain Identity rules . Give an example using the identity rules for

the simplification.

5. Construct Regular grammar for the given Finite Automata. Apply 7

6. Use G be the grammar

K method)

For the string aaabbabbba ,

 Find

S aB bA

A a aS bAA

B b  bS aBB

a. Leftmost Derivation.

b . Rightmost Derivation.

c. Derivation Tree.

7. Explain the properties, applications of Context Free Languages Understand 8

8. Construct right linear and left linear grammars for given Regular

Expression.

9. Construct a Transition System M accepting L(G) for a given

Regular Grammar G.

10. Discuss the properties of Context free Language. Explain the

pumping lemma with an example.

Unit-3

1. Write a short notes on Chomsky Normal Form and Griebach Normal

Form.

2. Show that the following grammar is ambiguous with respect to the

string aaabbabbba.

3. Use the following grammar :

SaB | bA

AaS| bAA| a

BbS | aBB | b

SABC | BbB

AaA | BaC|aaa

BbBb| a|D

CCA|AC

Dɸ

Eliminate ε-productions.

Eliminate any unit productions in the resulting grammar.

Eliminate any useless symbols in the resulting grammar.

Convert the resulting grammar into Chomsky Normal Form

4. Illustrate the construction of Griebach normal form with an example. Apply 9

5. Show that the following CFG ambiguous.

 Cb

6. Discuss the Pumping lemma for Context Free Languages concept

with example

8. Construct a PDA to accept the language L ={ a

by a final state. Draw the graphical representation of the PDA.

Also show the moves made by the PDA for the string aaabbb

9. Construct NPDA for L = { W WR

M = ({q1,q2},{0,1}.{R,B,G},δ,q1,R,φ}

10. Write the procedure to convert from the given PDA to a CFG.

Convert the following example.

δ(q0,b,z0)={q0,zz0)

δ(q0, b, z)=(q0,zz)

δ(q0, ε ,z0)=(q0,ε)

δ(q0,a,z) = (q1,z)

δ(q1,b,z)=(q1,ε)

 δ(q1,a,z0)=(q0,z0)