- 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, m3}
- 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
0 comments:
Post a Comment