Scribd
Upload
2 views2 pages

TOC_assignment_2

The document is an assignment with instructions to submit a handwritten work by July 9, 2026, covering various topics in formal languages and automata theory. It includes questions on regular expressions, finite automata, the pumping lemma, context-free grammars, and pushdown automata. Students are required to provide definitions, construct automata, and prove properties of languages.

Uploaded by

sallapuramkarthik.221cs243
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

TOC_assignment_2

The document is an assignment with instructions to submit a handwritten work by July 9, 2026, covering various topics in formal languages and automata theory. It includes questions on regular expressions, finite automata, the pumping lemma, context-free grammars, and pushdown automata. Students are required to provide definitions, construct automata, and prove properties of languages.

Uploaded by

sallapuramkarthik.221cs243
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

Assignment 2

Instructions:
• Submit a handwritten assignment on or before 9 July 2026.

• Answer all questions clearly. Draw diagrams wherever required.

1. Define a regular expression. Explain the meaning of union, concatenation, and Kleene star
with examples.

2. Construct a finite automaton for the regular expression

(0 + 1)∗ 00(0 + 1)∗ .

3. Convert the following NFA into an equivalent DFA using subset construction. Clearly show all
DFA states and final states.
The NFA is defined as follows:

Q = {q0 , q1 , q2 }, Σ = {0, 1}, q0 is the start state, F = {q2 }.

The transition function is:

δ(q0 , 0) = {q0 , q1 }, δ(q0 , 1) = {q0 },

δ(q1 , 0) = ∅, δ(q1 , 1) = {q2 },


δ(q2 , 0) = ∅, δ(q2 , 1) = ∅.

4. Explain the equivalence between DFA, NFA, and regular expressions. What class of languages
do they describe?

5. Given two regular languages L1 and L2 , explain why L1 ∩ L2 is also regular.

6. State the pumping lemma for regular languages. Explain the meaning of pumping length.

7. Use the pumping lemma to prove that the language

L = {0n 1n | n ≥ 0}

is not regular.

8. Use the pumping lemma to prove that the language

L = {ww | w ∈ {0, 1}∗ }

is not regular.

9. Define a context-free grammar. Explain its four components with an example.

10. Give a context-free grammar for the language

L = {0n 1n | n ≥ 0}.

Also derive the string 000111.

11. Construct context-free grammars for the following languages:

1
(a) L = {0n 1m | n, m ≥ 0}
(b) L = {0n 1n | n ≥ 0}
(c) L = {w ∈ {0, 1}∗ | w is a palindrome}
(d) L = {an bn cm | n, m ≥ 0}

12. Consider the grammar:


S → 0S1 | A
A → 1A | ϵ
Answer the following:

(a) Generate five strings from this grammar.


(b) Give the leftmost derivation of 00111.
(c) Give the rightmost derivation of 00111.
(d) Describe the language generated by the grammar.

13. What is an ambiguous grammar? Give an example of an ambiguous grammar.

14. Define a pushdown automaton. Explain the role of the stack in a PDA.

15. Construct a PDA for the language

L = {0n 1n | n ≥ 0}.

Explain how the PDA uses its stack.

You might also like