Scribd
Upload
16 views2 pages

TAFL Question Bank

The document outlines various topics related to automata theory, formal languages, and Turing machines, including definitions, modifications, grammar constructions, and problem-solving questions. It includes tasks such as constructing context-free grammars, designing Turing machines, and proving the Pumping Lemma. Additionally, it emphasizes the importance of understanding different types of automata and their applications.

Uploaded by

roshni97777
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views2 pages

TAFL Question Bank

The document outlines various topics related to automata theory, formal languages, and Turing machines, including definitions, modifications, grammar constructions, and problem-solving questions. It includes tasks such as constructing context-free grammars, designing Turing machines, and proving the Pumping Lemma. Additionally, it emphasizes the importance of understanding different types of automata and their applications.

Uploaded by

roshni97777
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

INSTITUTE OF TECHNOLOGY& MANAGEMENT

Integrated Technical Campus: Engineering, Pharmacy & Management


Approved by AICTE, Pharmacy Council of India, New Delhi & Affiliated to Dr. APJAKTU, Lucknow
AL-1, Sector - 7, GIDA, Gorakhpur -273209 (UP)

1. Define Greibach normal form.


2. Explain the modification done in Finite Automaton (FA) to make it PDA.
3. Discuss the halting problem of Turing Machine.
4. Construct the context free grammar (CFG) for the language {ancbn | n>=1}
5. Check whether the grammar is ambiguous or not. R R+R | RR | R*| a | b | c.

Obtain the string w = a+b*c.

6. Eliminate unit productions in the grammar. S A | bb A B | b B S | a.

7. Define Chomsky normal form.

8. Explain the modification done in Finite Automaton (FA) to make it Turing Machine.

9. Explain Universal Turing Machine.

10. Show that the context-free grammar G given by productions S → SBS | a, B → b, is ambiguous.

Q11. Construct a CFG for the following language L = {ambn | m!=n}

Q12. Does the PCP with two lists X= {10, 011, 101} and Y= {101, 11, 011} have a solution?

Q13. Construct the regular grammar for the language: L {anbm | n, m >=1}

Q14. Design a Turing machine for the language L= {anbncn |n>=1}.

Q15. Construct a context free grammar G which accepts N(A), where A = ({q0, q1}, {a, b}, {z0, z},δ, q0,
z0, Ø) and is given by as :

δ(q0, b, z0)= {(q0, zz0)} δ(q0,ε, z0)= {(q0, ε)} δ(q0, b, z)= {(q0, zz)}

δ(q0, a, z)= {(q1, z)} δ(q1, b, z)= {(q1, ε)} δ(q1, a, z0)= {(q0, z0)}

Q15. Obtain PDA to accept all strings generated by the language {a nbman | m, n >= 1}. And generate
ID for aabaa.

Q16. Is {0n1n2n | n>=1} recognized by PDA or not? If not, why?

Q17. Construct a regular grammar for L = {0n11 | n>=1}.

Q18. State and Prove Pumping Lemma of RE. Show that L = {a p: p is a prime} is not regular?

Q19. Design Turing machine to recognize the language {0 n1n | n>=1}.

Q20. Explain Chomsky hierarchy of Languages.

Q21. Construct a Turing Machine for the function f (x) = m + n.


Q 22. Design PDA for palindrome strips over input {a, b}.

Q 23. Define the term ‘Automata’ with an example. What are the types of Automata?

Q 24. Differentiate between the Mealy machine and Moore machine.

Q 25. Construct a DFA accepting all string over {0, 1} having odd number of 0’s.

Q 26. Define Regular Expression.

Q 27. Differentiate between the DFA and NDFA.

Q 28. Design a machine which accept the language

L= {w1 ab w2: w1, w2 ε (a, b)*}.

Q 29. Consider a graph containing null-move given in Fig. Obtain an equivalent without null-moves.

And All Home Work, Assignment and Model Paper Questions…

Best of Luck

You might also like