KEMBAR78
Formal Language Theory Exercises | PDF | Theoretical Computer Science | Applied Mathematics
Scribd
Upload
214 views2 pages

Formal Language Theory Exercises

This document contains 11 problems related to formal language theory. The problems involve finding regular grammars and expressions, minimal deterministic finite automata (DFAs), non-deterministic finite automata (NFAs), and context-free grammars for various languages involving strings of symbols. The problems cover topics such as regular expressions, equivalence of regular expressions, DFA and NFA construction, and right and left linear grammars.

Uploaded by

subramanyam62
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
214 views2 pages

Formal Language Theory Exercises

This document contains 11 problems related to formal language theory. The problems involve finding regular grammars and expressions, minimal deterministic finite automata (DFAs), non-deterministic finite automata (NFAs), and context-free grammars for various languages involving strings of symbols. The problems cover topics such as regular expressions, equivalence of regular expressions, DFA and NFA construction, and right and left linear grammars.

Uploaded by

subramanyam62
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

Formal Language Theory

Problem Sheet 1
1. Find Regular Grammars for the following languages on {a, b}
(a) L = {w : na (w) and nb (w) are both even}.
(b) L = {w : (na (w) − nb (w)) mod 3 = 1}.
(c) L = {w : (na (w) − nb (w)) mod 3 6= 0}.
2. Find a regular grammar that generates the set of all Pascal real numbers.

3. Find the minimal DF A for the following languages


(a) L = {an bm : n ≥ 2, m ≥ 1}.
(b) L = {an b : n ≥ 0} ∪ {bn a : n ≥ 1}.
(c) L = {an : n ≥ 0, n 6= 3}.
4. Find regular expression for the set {an bm : (n + m) is even}.
5. Give a regular expression for the following languages:
(a) L = {an bm : n ≥ 4, m ≤ 3}.
(b) L = {an bm : n ≥ 1, m ≥ 1, nm ≥ 3}.
(c) L = {abn w : n ≥ 3, w ∈ {a, b}+ }.
(d) L = {w ∈ {0, 1}∗ : w has exactly one pair of consecutive zeros}.
(e) L = {w ∈ {0, 1}+ : w ends with 01}.
(f) L = {w ∈ {0, 1}+ : |w|0 = even}.
6. Prove the following:
(a) (r1∗ )∗ ≡ r1∗ .
(b) r1∗ (r1 + r2 )∗ ≡ (r1 + r2 )∗ .
(c) (r1 + r2 )∗ ≡ (r1∗ r2∗ )∗ .
for all regular expression r1 andr2 . Here ≡ stands for equivalence in the
sense of the language generated.
7. Find an N F A that accepts the language L(aa∗ (a + b)).
8. Find DF A that accepts the following languages:
(a) L(aa∗ + aba∗ b∗ ).
(b) L(ab(a + ab)∗ + (a + aa)).
(c) L((abab)∗ + (aaa∗ + b)∗ ).
(d) L(((aa∗ )∗ b)∗ ).
9. Construct a DF A that accepts the language generated by the grammar

S → abA
A → baB
B → aA/bb

1
10. Construct right and left linear grammars for the following language:

L = {an bm : n ≥ 2, m ≥ 3}

11. Construct a right linear grammar for the following language:

L((aab∗ ab)∗ )

You might also like