Scribd
Upload
2 views2 pages

Automata Theory Mid-Sem Exam Practice

This document is a tutorial practice sheet for a mid-semester exam in Automata Theory for B.Tech 2nd Year students. It includes questions on finite automata, regular expressions, the Pumping Lemma, context-free grammars, and additional conceptual comparisons between regular and context-free languages. Students are instructed to solve each question with proper explanations and justifications.

Uploaded by

abhinav12378
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
2 views2 pages

Automata Theory Mid-Sem Exam Practice

This document is a tutorial practice sheet for a mid-semester exam in Automata Theory for B.Tech 2nd Year students. It includes questions on finite automata, regular expressions, the Pumping Lemma, context-free grammars, and additional conceptual comparisons between regular and context-free languages. Students are instructed to solve each question with proper explanations and justifications.

Uploaded by

abhinav12378
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

Tutorial Practice Sheet for Mid-Semester Exam

Subject: Automata Theory

[Link] 2nd Year

---

Section I: Finite Automata

1. Define a Deterministic Finite Automaton (DFA) and a Non-Deterministic Finite Automaton (NFA). How do they differ?
Explain with examples.
2. Construct a DFA for the language L = { w | w contains an even number of 0's and an odd number of 1's over the
alphabet {0,1} }.
3. Convert the given NFA to an equivalent DFA (given in the document).
4. Explain the concept of an epsilon-move in an NFA. Provide an example of NFA to DFA conversion.
5. Differentiate between Moore and Mealy Machines. Convert the given Mealy Machine to a Moore Machine.

---

Section II: Regular Expressions and Languages

6. Define a regular expression. Construct a regular expression for L = { w | w starts with '01' and ends with '10' over {0,1}
}.
7. Prove that L = { 0^n1^n | n >= 0 } is not regular using the Pumping Lemma.
8. Convert the given regular expression (a|b)*abb into an NFA.
9. Describe the steps to minimize a DFA and apply the method to the given DFA.

---

Section III: Pumping Lemma for Regular Sets

10. State and explain the Pumping Lemma for regular languages. How can it be used to prove that a language is not
regular?
11. Use the Pumping Lemma to show that L = { a^n b^n c^n | n >= 1 } is not regular.
12. Prove that L = { w | w is a palindrome over {0,1} } is not regular using the Pumping Lemma.
---

Section IV: Context-Free Grammar (CFG) and Languages

13. Define a Context-Free Grammar (CFG). Design a CFG for L = { a^n b^m | n, m >= 1 }.
14. Differentiate between ambiguous and unambiguous grammars. Give an example of ambiguity.
15. Construct a derivation tree for the string "aabb" using a given CFG.
16. Show that the grammar S -> SS | (S) | epsilon is ambiguous by deriving two parse trees for "(())()".
17. Explain the relationship between derivations and derivation trees.

---

Additional Conceptual Questions

18. Compare and contrast regular languages and context-free languages.


19. Why are regular languages closed under union, intersection, and complement operations? Explain with examples.
20. Prove that L = { w | w has an equal number of a's and b's } is not regular.

---

This practice sheet contains conceptual and problem-solving questions. Solve each question with proper explanations
and justifications. Best of luck!

You might also like