What is NFA? How is it different from DFA? How is NFA to DFA conversion done? Convert the following NFA into DFA.

How does Turing machine accept a string? Design a Turing Machine over the alphabet {0,1,a} that processes the string defined by L = {a01a,a10a,a0101a}. Show both transition diagram and table. Show acceptance of a0101a.

Define context free grammar with an example. Explain with example, how context free grammar is converted to Chomsky Normal Form.

Define string, substring, empty string, and empty language over alphabet {a,b}.

Design a DFA that accepts single line and multi-line comments of the C-Language.

Write regular expression over {a,b} that represents

a. Strings having exactly two a’s and atleast two b’s.

b. Strings having an even number of a’s and each a followed by at least one b.

Using pumping lemma, prove that the language L = {aⁱb^jc^k | j=i+k} is not regular.

Design a PDA over {x,y} which accepts strings defined by the language L = {xⁿyⁿxy | n>=0}. Show acceptance of xyxy.

Design a Turing machine that computes a function f(n)=0.

How abstract, decision and optimization problems are different from each other?

How is PDA to CFG conversion done? Consider a PDA that accepts by empty stack, P=({p,q},{0,1},{Z},δ,p,z); with δ defined as

δ(p,0,z)=(p,0z), δ(p,0,0)=(p,00), δ(p,1,0)=(p,ε), δ(p,ε,z)=(q,ε),

Now construct an equivalent CFG.

What is the meaning of the term “Context Free” in context free grammar? Justify with a suitable example. What is the need of a parse tree?