DFA Exercises
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