Here are the some of the Formal Language and Automata Theory(Flat) Short answer questions.

as many a’s and b’s.

a) What are Universal Turing Machines

b) Define computations of a TM?

c) Define CFG and What are its advantages

d) Define unit production.

e) Find all strings in L ((a+b)*b(a+ab)*) of length less than four

f) Compare NFA & DFA

g) Write a note on applications of formal languages and automata.

h) Define regular expression ,Give a regular expression for L={anbm : n 4, m3}

a) Give a description about FA with empty moves

b) Define regular grammar with example.

c) Give the set and explain in English the sets denoted by following regular expressions.

i) (11+0) (00+1)

ii) (1+01+001)(0+00)

iii) (0+1)00(0+1)

iv) 0 1 2

v) 00 11 22

d) Explain dependency graph & its applications in CFG.

e) Prove the substitution rule of context free grammar?

f) Give a CFG generating the following set that is the set of palindromes over alphabet{a,b}

g) Let G be the grammar

a) Find the DFA that recognizes the set of all string on Σ={a,b} starting with the prefix “ab”

b) Construct a DFA & NFA to accept all string in {a,b} such that every “a” has one “b” immediately 8 to its right ?

c) Find all strings in L ((a+b)*b(a+ab)*) of length less than four

d) Prove the following identities for regular expression r,s and t here r=s means 6

L(r)=L(s) r+s=s+r, (rs)t=r(st),(r+s)t=rt+st

e) Find the NFA that accepts the language L{ab*aa+bba*ab)

f) What are CFG’s Give CFG for the language L= {an b2n | n>0}

g) Define context free grammars formally. Give some examples .

h) Why FAs are less powerful than the PDA’s

**>**Define the terms alphabet, string, prefix, suffix, language give examples to each.**>**Give DFA & NFA which accept the language { (10)n : n 0 }**>**Define a linear grammar**>**Define a ambiguous CFG**>**Construct a CFG for the set of all strings over the alphabet {a,b} with exactly twice 10as many a’s and b’s.

**>**Distinguish between DPDA and NPDA**>**Explain the operations of a NPDA with diagram?**>**Define unrestricted grammar.**>**What is the modified version of PCPa) What are Universal Turing Machines

b) Define computations of a TM?

c) Define CFG and What are its advantages

d) Define unit production.

e) Find all strings in L ((a+b)*b(a+ab)*) of length less than four

f) Compare NFA & DFA

g) Write a note on applications of formal languages and automata.

h) Define regular expression ,Give a regular expression for L={anbm : n 4, m3}

**>**Prove or disprove the following for regular expressions r,s,and t (rs+r)r=r(sr+r)*a) Give a description about FA with empty moves

b) Define regular grammar with example.

c) Give the set and explain in English the sets denoted by following regular expressions.

i) (11+0) (00+1)

ii) (1+01+001)(0+00)

iii) (0+1)00(0+1)

iv) 0 1 2

v) 00 11 22

d) Explain dependency graph & its applications in CFG.

e) Prove the substitution rule of context free grammar?

f) Give a CFG generating the following set that is the set of palindromes over alphabet{a,b}

g) Let G be the grammar

a) Find the DFA that recognizes the set of all string on Σ={a,b} starting with the prefix “ab”

b) Construct a DFA & NFA to accept all string in {a,b} such that every “a” has one “b” immediately 8 to its right ?

c) Find all strings in L ((a+b)*b(a+ab)*) of length less than four

d) Prove the following identities for regular expression r,s and t here r=s means 6

L(r)=L(s) r+s=s+r, (rs)t=r(st),(r+s)t=rt+st

e) Find the NFA that accepts the language L{ab*aa+bba*ab)

f) What are CFG’s Give CFG for the language L= {an b2n | n>0}

g) Define context free grammars formally. Give some examples .

h) Why FAs are less powerful than the PDA’s

This comment has been removed by a blog administrator.