October 14, 2020
- Write the name of different types of grammer?
- Explain Chomsky classification of grammer?
- Convert into GNF?
- Write closure property of context free language and also write decision algorithm for CFL?
- Define derivation and language.
- Construct a reduced grammar equivalent to the grammar
- Construct a grammar like greibach normal form
- Consider the grammar:
S=S+S/S*S/id
Construct leftmost
derivation, rightmost derivation and derivation tree for the string
W=id+id*id
- Define grammar?
- Define context free grammars?
- Write a CFG which generates the string of balanced parenthesis. Also show that the following group of parenthesis is accepted by the CFG
(()((())))
- What do you mean by ambiguity in context free grammars. If G is the grammar S->SbS|a, then show that G is ambiguous
- Write the name of different grammars.
- Expain pumping lemma for context free language with examples.
- Consider the grammar S->S+S|S*S|a|b
- Construct leftmost derivation, right most derivation and derivation tree for the string ab+c. also show that the grammar is ambiguous.
- Explain relation among types of grammars.
- Context free
language L:{WCWR|W
C(0+1)*} can be accepted by which automaton.
1.PDA, 2.NPDAM,
3.TM, 4.ALL
- Explain deterministic and nondeterministic push down automata with example.
- design a turing machine m to recognize the language:
{1n2n3n
| n>=1}
- Define PCP and MPCP. Does the PCP with two lists:
X=(b, bab3,
ba) and
Y=(b3,ba,a) have a solution.
Y=(b3,ba,a) have a solution.
