Here are the some of the Formal Language and Automata Theory(Flat) Short answer questions.
>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 10
as 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 PCP
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}
>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
>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 10
as 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 PCP
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}
>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.
ReplyDelete