DFA Exercise
DFA Exercises
1. Give a DFA for Σ = {0 1} and strings that have an odd number of 1’s and any number
of 0’s.
of 0’s.
2. Give a DFA for Σ = {a; b; c} that accepts any string with aab as a substring.
3. Give a DFA for Σ = {a; b} that accepts any string with aababb as a substring.
4. Suppose you are given many texts (strings) T1; : : : ; Tn and one pattern string P. You
want to determine which texts have the pattern P as a substring. What is the total
runtime of doing this using DFAs?
want to determine which texts have the pattern P as a substring. What is the total
runtime of doing this using DFAs?
5. Draw a DFA for the language 'all strings with 011 as a substring', over sigma={0, 1}
6. Design DFA which accepts language L = {0,000,00000,……} over {0}
7. Design a DFA for the language L = {ban/ n ≥0}.
8. Design DFA over {a,b} to accept strings which does not contains two consecutive b's
9. Design a DFA (deterministic finite automaton) to accept the language L1 = nα ∈ {a, b, c}∗ | α starts and ends with the same symbol
10. Let Σ = {a; b}. Construct a DFA for the languages
1. { x 2 Σ* | x starts with three consecutive a’s}.
2. { x 2 Σ* | x contains a substring of three consecutive a’s}.
3. { x 2 Σ* | length of the string x is even}.
4. { x 2 Σ* | length of the string x is divisible by 3}.
5. { x 2 Σ* | length of the string x is divisible by 2 or 3}.
1. { x 2 Σ* | x starts with three consecutive a’s}.
2. { x 2 Σ* | x contains a substring of three consecutive a’s}.
3. { x 2 Σ* | length of the string x is even}.
4. { x 2 Σ* | length of the string x is divisible by 3}.
5. { x 2 Σ* | length of the string x is divisible by 2 or 3}.
11. Can you construct an DFA for the languages given below:
1. {anbn | 1 ≤ n ≤ 5}.
2. {anbn | 1 ≤ n ≤ 100}.
3. {(ab)n | 1 ≤ n ≤ 100}.
4. {anbn| n ≥ 1}.
5. {(ab)n | n ≥ 1}.
1. {anbn | 1 ≤ n ≤ 5}.
2. {anbn | 1 ≤ n ≤ 100}.
3. {(ab)n | 1 ≤ n ≤ 100}.
4. {anbn| n ≥ 1}.
5. {(ab)n | n ≥ 1}.
Comments
Post a Comment