FLAT 2 & 3 marks Important Questions

• a) Define the terms alphabet, string, prefix, suffix, language give examples to each.
• b) Give DFA & NFA which accept the language { (10)n : n 0 }
• c) Define a linear grammar
• d) Define a ambiguous CFG
• e) 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.
• f) Distinguish between DPDA and NPDA
• g) Explain the operations of a NPDA with diagram?
• h) Define unrestricted grammar.
• i) 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, m3}
• i) 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
•