Cases of DFA, NFA, RE, Grammar, CFG, Meelay, Moorey, Problems, and PDA.
All marked with are verified individually. Hover over the icon to know who verified it. Those without the ticks may contain error. If you have knowledge about it, let us know and we will verify it with your name.
If you spot any errors. Message us.
Accept Every String
Construct an DFA over an input $\{a,b\}$, that accepts every string.
DFA
finite_state_machine 0 0 0->0 a,b secret_node->0
NFA
finite_state_machine 0 0 0->0 a,b secret_node->0
Regular Expression
$(a+b)^*$
Grammar
$S \rightarrow aS | bS | \lambda$
Accept every string without $\epsilon$
Construct an DFA over an input $\{a,b\}$, that accepts every string without $\epsilon$.
DFA
finite_state_machine 1 1 1->1 a,b 0 0 secret_node->0 0->1 a,b
NFA
1
2
a,b
ε
Regular Expression
$(a+b)(a+b)^*$
Grammar
$S \rightarrow aS | bS | a | b$
Start with a
Construct an DFA over an input $\{a,b\}$, that starts with a.
DFA
Accept everything ε 1 1 1->1 a,b 0 0 secret_node->0 0->1 a 2 2 0->2 b 2->2 a,b
NFA
0 1 a a,b
Regular Expression
$a(a+b)^*$
Grammar
$S \rightarrow aA$ $A \rightarrow aA | bA | \lambda$
End with b
Construct an DFA over an input $\{a,b\}$, that ends with b.
DFA
finite_state_machine 1 1 1->1 b 0 0 secret_node->0 0->1 b 0->1 a 0->0 a
NFA
0 1 b a,b
Regular Expression
$(a+b)^*b$
Grammar
$S \rightarrow Ab$ $A \rightarrow aA | bA | \lambda$
Start with a
and end with b
Construct an DFA over an input $\{a,b\}$, that starts with a and ends with b.
DFA
finite_state_machine 1 1 1->1 b 2 2 1->2 a 0 0 secret_node->0 0->2 a 3 3 0->3 b 2->1 b 2->2 a 3->3 a,b
NFA
0 1 2 a b a a,b
Regular Expression
$a(a+b)^*b$
Grammar
$S \rightarrow aAb$ $A \rightarrow aA | bA | \lambda$
Start with a
or end with b
Construct an DFA over an input $\{a,b\}$, that starts with a or ends with b.
DFA
finite_state_machine 2 2 2->2 b 1 1 2->1 a 3 3 3->3 a,b 0 0 secret_node->0 0->2 b 0->3 a 1->2 b 1->1 a
NFA
0 1 a,b a,b
Regular Expression
$a(a+b)^* + (a+b)^*b$
Grammar
$S \rightarrow aA | Ab$ $A \rightarrow aA | bA | \lambda$
Number of b
is exactly three in every string
Construct an DFA over an input $\{a,b\}$, that has exactly three b's in every string.
DFA
0 1 2 3 4 b b b b a,b a a a a ε
NFA
0 1 2 3 b b b
Regular Expression
$(a+b)^*b(a+b)^*b(a+b)^*b(a+b)^*$
Grammar
$S \rightarrow aS | bA$ $A \rightarrow aA | bB$ $B \rightarrow aB | bC$ $C \rightarrow aC | \lambda$
Length of 'b
' is atleast three
Construct an DFA over an input $\{a,b\}$, that has atleast three b's in every string.
DFA
finite_state_machine 3 3 3->3 a,b 0 0 secret_node->0 0->0 a 1 1 0->1 b 0->1 a 2 2 0->2 a 1->2 b 2->3 b
NFA
0 1 2 3 b b b b
Regular Expression
$(a+b)^*bbb(a+b)^*$
Grammar
$S \rightarrow aS | bA$ $A \rightarrow aA | bB$ $B \rightarrow aB | bC$ $C \rightarrow aC | bC | \lambda$
Length of string is exactly 4
Construct an DFA over an input $\{a,b\}$, that has exactly four characters in every string.
DFA
finite_state_machine 1 1 5 5 1->5 a,b 0 0 secret_node->0 4 4 0->4 a,b 3 3 4->3 a,b 2 2 2->1 a,b 3->2 a,b 5->5 a,b
NFA
0 1 2 3 5 a,b a,b a,b a.b
Regular Expression
$(a+b)(a+b)(a+b)(a+b)$
Grammar
$S \rightarrow AAAA $ $A \rightarrow a | b$
Length of b
is atleast 4
Construct an DFA over an input $\{a,b\}$, that has atleast four b's in every string.
DFA
finite_state_machine 4 4 4->4 a,b 0 0 secret_node->0 0->0 a 1 1 0->1 b 0->1 a 2 2 0->2 a 3 3 0->3 a 1->2 b 2->3 b 3->4 b
NFA
0 1 2 3 5 b b b b b
Regular Expression
$(a+b)^*bbbb(a+b)^*$
Grammar
$S \rightarrow aS | bA$ $A \rightarrow aA | bB$ $B \rightarrow aB | bC$ $C \rightarrow aC | bD$ $D \rightarrow aD | bD | \lambda$
Length of string is atmost four
Construct an DFA over an input $\{a,b\}$, that has atmost four characters in every string.
DFA
finite_state_machine 0 0 2 2 0->2 a,b 1 1 5 5 1->5 a,b 3 3 2->3 a,b 4 4 3->4 a,b 4->1 a,b secret_node->0 5->5 a,b
NFA
0 1 2 3 5 a,b a,b a,b a.b
Regular Expression
$\epsilon + a+b + (a+b)(a+b) + (a+b)(a+b)(a+b) + (a+b)(a+b)(a+b)(a+b)$
Grammar
$S \rightarrow AAAA$ $A \rightarrow \lambda | a | b$
Number of a
is even
DFA
finite_state_machine 0 0 2 2 0->2 b 1 1 0->1 a 0->1 a secret_node->0 2->2 b 2->1 a 1->1 b
NFA
Regular Expression
$(b^*ab^*a)^*$
Grammar
$S \rightarrow BB$ $B \rightarrow aBa | \lambda | bB$
Length of string is divisible by 2
or length of string is even
DFA
finite_state_machine 0 0 1 1 0->1 0,1 0->1 0,1 secret_node->0
NFA
Regular Expression
$((0+1)(0+1))^*$
Grammar
$S \rightarrow SS | 00 | 01 | 10 | 11 | \lambda$
Length of string is divisible by 4
DFA
finite_state_machine 0 0 3 3 0->3 0,1 1 1 0->1 0,1 secret_node->0 2 2 3->2 0,1 2->1 0,1
NFA
Regular Expression
$((0+1)(0+1)(0+1)(0+1))^*$
Grammar
Number of b
is odd
DFA
finite_state_machine 1 1 1->1 a 0 0 secret_node->0 0->1 b 0->1 b 0->0 a
NFA
Regular Expression
$(a^*ba^*b)^*a^*ba^*$
Grammar
$S \rightarrow aS | A$ $A \rightarrow bB$ $B \rightarrow aB | bAb | \lambda$
Length of string
is odd
DFA
finite_state_machine 1 1 0 0 secret_node->0 0->1 a,b 0->1 a,b
NFA
Regular Expression
$(a+b)((a+b)(a+b))^*$
Grammar
$S \rightarrow CB$ $C \rightarrow AC | \lambda$ $A \rightarrow BB$ $B \rightarrow a | b$
Length of string is divisible by 3
Construct an DFA over an input $\{a,b\}$, where length of string is divisible by 3.
DFA
finite_state_machine 0 0 2 2 0->2 a,b 1 1 0->1 a,b secret_node->0 2->1 a,b
NFA
Regular Expression
$((a+b)(a+b)(a+b))^*$
Grammar
$S \rightarrow AS | \lambda$ $A \rightarrow BBB$ $B \rightarrow a | b$
Length of string is divisible by 3 remainder 2
DFA
finite_state_machine
2
2
0
0
secret_node->0
0->2
a,b
1
1
0->1
a,b
1->2
a,b
NFA
Regular Expression
$((a+b)(a+b)(a+b))^*(a+b)(a+b)$
Grammar
$S \rightarrow abcA | bacA | acbA | bcaA | cabA | cbaA$ $A \rightarrow aa | bb | cc$ $abcA \rightarrow aSbcA | abScA | abcAS$ $bacA \rightarrow baScA | bSacA | bacAS$ $acbA \rightarrow aScbA | acbAS | acSbA$ $bcaA \rightarrow bScaA | bcSaA | bcaAS$ $cabA \rightarrow caSbA | cSabA | cabAS$ $cbaA \rightarrow cbSaA | cbaAS | cSbaA$ $S \rightarrow \lambda$
Last 2 symbols are same
DFA
finite_state_machine 2 2 2->2 b 3 3 2->3 a 4 4 4->4 a 1 1 4->1 b 0 0 secret_node->0 0->3 a 0->1 b 3->4 a 3->1 b 1->2 b 1->3 a
NFA
0 1 2 3 b b a a a,b
Regular Expression
$(a+b)^*(aa+bb)$
Grammar
$S \rightarrow aS | bS | aa | bb$
First 2 symbols are same
DFA
finite_state_machine 1 1 1->1 a,b 0 0 secret_node->0 3 3 0->3 a 2 2 0->2 b 3->1 a 4 4 3->4 b 2->1 b 2->4 a 4->4 a,b
NFA
Regular Expression
$(aa+bb)(a+b)^*$
Grammar
$S \rightarrow aaA | bbA$ $A \rightarrow aA | bA | \lambda$
Last 2 symbols are different
DFA
finite_state_machine 2 2 3 3 2->3 b 4 4 2->4 a 3->2 a 1 1 3->1 b 0 0 secret_node->0 0->4 a 0->1 b 4->3 b 4->4 a 1->2 a 1->1 b
NFA
0 1 2 3 b a a b a,b
Regular Expression
$(a+b)^*(ab+ba)$
Grammar
$S \rightarrow aS | bS | ab | ba$
Start and end with same symbol
DFA
finite_state_machine 1 1 1->1 b 2 2 1->2 a 4 4 4->4 a 3 3 4->3 b 0 0 secret_node->0 0->1 b 0->4 a 2->1 b 2->2 a 3->4 a 3->3 b
NFA
Regular Expression
$a(a+b)^*a + b(a+b)^*b$
Grammar
$S \rightarrow aAa | bBb$ $A \rightarrow aA | bA | \lambda$ $B \rightarrow aB | bB | \lambda$
Start and end with different symbol
DFA
finite_state_machine
2
2
2->2
a
1
1
2->1
b
3
3
3->3
b
4
4
3->4
a
0
0
secret_node->0
0->4
a
0->1
b
4->3
b
4->4
a
1->2
a
1->1
b
NFA
Regular Expression
$a(a+b)^*b + b(a+b)^*a$
Grammar
$S \rightarrow aAb | bAa$ $A \rightarrow aA | bA | \lambda$
Number of a
is even and number of b
is odd
DFA
13
14
23
24
a
a
b
b
b
b
a
a
ε
NFA
Regular Expression
$(b^*ab^*a)^*b(b^*bb^*b)^*$
$(aa)*(bb)*$
Grammar
$S \rightarrow BB$ $B \rightarrow aBa | A$ $A \rightarrow bBb | \lambda$
Number of a
is even and b
is even
DFA
13
14
23
24
a
a
b
b
b
b
a
a
ε
NFA
Regular Expression
$((a^*ba^*b)^*a^*a)^*$
Grammar
$S \rightarrow BB$ $B \rightarrow aBa | bBb | \lambda$
Number of 1
's odd followed by number of 0
s odd
DFA
finite_state_machine 1 1 2 2 1->2 0 4 4 1->4 1 0 0 secret_node->0 3 3 0->3 1 0->3 1 0->4 0 3->1 0 2->1 0 2->4 1 4->4 1,0
NFA
Regular Expression
$1(11)^*0(00)^*$
Grammar
$S \rightarrow 0A | 1B$ $A \rightarrow 0A0 | 1A1 | 0$ $B \rightarrow 0B0 | 1B1 | \lambda$
Start with 0 and have odd length string start with 1 and have even length string
DFA
finite_state_machine 1 1 2 2 1->2 0,1 0 0 secret_node->0 0->1 0 0->2 1 2->1 0,1
NFA
Regular Expression
$0((0+1)(0+1))^* + 1(0+1)((0+1)(0+1))^*$
Grammar
$S \rightarrow 0A | 1B$ $A \rightarrow 0A0 | 1A1 | 0$ $B \rightarrow 0B0 | 1B1 | \lambda$
Every string whose substring Accept '001'
DFA
finite_state_machine 3 3 3->3 0,1 0 0 secret_node->0 0->0 1 1 1 0->1 0 0->1 1 2 2 1->2 0 2->3 1 2->2 0
NFA
Regular Expression
$(0+1)^*001(0+1)^*$
Grammar
$S \rightarrow 0S | 1S | 001$ $S \rightarrow 0A | 1A | A$ $A \rightarrow 00B$ $B \rightarrow 01$
Trybit as substring
DFA
finite_state_machine 3 3 3->3 0,1 0 0 secret_node->0 4 4 0->4 0 1 1 0->1 1 4->1 1 5 5 4->5 0 1->4 0 2 2 1->2 1 2->3 1 2->4 0 5->3 0 5->1 1
NFA
0 1 2 3 4 5 1 1 1 0 0 0
Regular Expression
$(0+1)^*(000+111)(0+1)^*$
Grammar
$S \rightarrow 0S | 1S | 000 | 111$
Accept all binary number divisible by 3
DFA
0
1
2
1
1
0
0
1
0
NFA
Regular Expression
Grammar
$S \rightarrow 0S | 1A | \lambda$ $A \rightarrow 0B | 1S$ $B \rightarrow 0A | 1C$ $C \rightarrow 0S | 1B$
3rd symbol is a
reading from left to right
Construct an DFA over an input $\{a,b\}$, where the 3rd symbol is $a$ reading from left to right.
DFA
finite_state_machine 1 1 1->1 a,b 0 0 secret_node->0 3 3 0->3 a,b 2 2 3->2 a,b 2->1 a 4 4 2->4 b 4->4 a,b
NFA
Regular Expression
$(a+b)(a+b)a(a+b)^*$
Grammar
$S \rightarrow AAaB$ $A \rightarrow a | b$ $B \rightarrow bB | aB | \lambda$
3rd symbol from left is 0
DFA
finite_state_machine
1
1
1->1
0,1
0
0
secret_node->0
3
3
0->3
0,1
2
2
3->2
0,1
2->1
0
4
4
2->4
1
4->4
0,1
NFA
Regular Expression
$(0+1)(0+1)0(0+1)^*$
Grammar
$S \rightarrow 00A | 01A | 10A | 11A$ $A \rightarrow 0$
L = {an bm | n,m >= 1}
DFA
finite_state_machine
1
1
1->1
b
3
3
1->3
a
0
0
secret_node->0
2
2
0->2
a
0->3
b
2->1
b
2->2
a
3->3
a,b
NFA
Regular Expression
$a^+b^+$
Grammar
$S \rightarrow aSb | ab$
L = {an bn | n $\geq$ 1}
DFA
Not Possible
PDA
q₀ q₁ q₂ a,Z₀ | aZ₀ a,a | aa b,a | ε b,a | ε ε,Z₀ | ε
L = {an bn cm | n,m $\geq$ 1}
DFA
Not Possible
PDA
q₀ q₁ q₃ q₂ a,Z₀ | aZ₀ a,a | aa b,a | ε b,a | ε c,Z₀ | Z₀ c,Z₀ | Z₀ ε,Z₀ | ε
L = {an+m bn cm | n,m $\geq$ 1}
DFA
Not Possible
PDA
q₀ q₁ q₃ q₂ a,Z₀ | aZ₀ a,a | aa b,a | ε b,a | ε c,a | ε c,a | ε ε,Z₀ | ε
L = {an bn+m cm | n,m $\geq$ 1}
DFA
Not Possible
PDA
q₀ q₁ q₃ q₂ a,Z₀ | aZ₀ a,a | aa b,a | ε b,a | ε c,b | ε c,b | ε ε,Z₀ | ε b,Z₀ | Z₀ b,b | bb
L = {an bm | n > m}
DFA
Not Possible
PDA
q₀ q₁ q₃ q₂ a,Z₀ | aZ₀ a,a | aa b,a | ε b,a | ε ε,a | ε ε,a | ε ε,Z₀ | ε
L = { an bm | n,m >=0}
DFA
finite_state_machine 0 0 0->0 a 1 1 0->1 b 1->1 b 2 2 1->2 a secret_node->0 2->2 a,b
NFA
$\epsilon$-NFA
b a ε
Regular Expression
$a^*b^*$
Grammar
$S \rightarrow aS | bS | \lambda$
L = { an bm cp dk | n,m,p,k >=0}
$\epsilon$-NFA
0 1 2 3 ε ε ε ε d c b a
Accept all substring of n length string W
$\epsilon$-NFA
0 1 2 3 a b c ε ε ε ε ε
L = { an bm | n,m >=0,1}
DFA
finite_state_machine
1
1
1->1
b
2
2
1->2
a
0
0
secret_node->0
0->1
b
0->0
a
2->2
a,b
NFA
Regular Expression
$a^*b^+$
Grammar
$S \rightarrow aS | bS | b$
L = {a2n | n>=1}
DFA
finite_state_machine
1
1
2
2
1->2
a
0
0
secret_node->0
0->2
a
2->1
a
NFA
Regular Expression
$(aa)^+$
Grammar
$S \rightarrow aaS | aa$
Not divisible by 3
DFA
0
1
2
1
1
0
0
1
0
NFA
Regular Expression
Grammar
$S \rightarrow aS | bS | A$ $A \rightarrow aa | bb | aA | bA$
Accept all string of 0,1 where each string end with '011'
DFA
finite_state_machine 3 3 1 1 3->1 0 0 0 secret_node->0 0->3 1 0->0 1 0->1 0 1->1 0 2 2 1->2 1 2->3 1 2->1 0
NFA
0 1 2 3 0 1 1 0,1
Regular Expression
$(0+1)^*011$
Grammar
$S \rightarrow 0S | 1S | A$ $A \rightarrow 01B$ $B \rightarrow 11$
Trybit as substring (000 or 111)
DFA
finite_state_machine
3
3
3->3
0,1
0
0
secret_node->0
4
4
0->4
0
1
1
0->1
1
4->1
1
5
5
4->5
0
1->4
0
2
2
1->2
1
2->3
1
2->4
0
5->3
0
5->1
1
NFA
Regular Expression
$(0+1)^*(000+111)(0+1)^*$
Grammar
$S \rightarrow aS | bS | 000 | 111$
Number of a
not multiple of 3
DFA
0 1 2 b b b a a a ε
NFA
Regular Expression
Grammar
$S \rightarrow aS | bS | A | B$ $A \rightarrow aa | bb | aA | bA$ $B \rightarrow aaaB | bbbB | \lambda$
Start with a
and substring ab
DFA
finite_state_machine
3
3
3->3
a,b
0
0
secret_node->0
1
1
0->1
a
4
4
0->4
b
1->1
b
2
2
1->2
a
2->3
b
2->2
a
4->4
a,b
NFA
Regular Expression
$a(a+b)^*ab(a+b)^*$
Grammar
$S \rightarrow aA$ $A \rightarrow aA | bA | abB$ $B \rightarrow aB | bB | \lambda$
Each string end with 010 or 101
DFA
finite_state_machine
3
3
4
4
3->4
0
1
1
3->1
1
4->3
1
5
5
4->5
0
0
0
secret_node->0
0->5
0
0->1
1
5->5
0
6
6
5->6
1
1->1
1
2
2
1->2
0
2->3
1
2->5
0
6->4
0
6->1
1
NFA
Regular Expression
$(0+1)^*(010+101)$
Grammar
$S \rightarrow 0S | 1S | A | B$ $A \rightarrow 010$ $B \rightarrow 101$
4th symbol is zero from left hand side
DFA
finite_state_machine 1 1 1->1 0,1 0 0 secret_node->0 4 4 0->4 0,1 3 3 4->3 0,1 2 2 2->1 0 5 5 2->5 1 3->2 0,1 5->5 0,1
NFA
Regular Expression
$(0+1)(0+1)(0+1)0(0+1)^*$
Grammar
$S \rightarrow aS | bS | aA | bA$ $A \rightarrow aB | bB$ $B \rightarrow aC | bC$ $C \rightarrow 0$
4th symbol is zero from right hand side
DFA
finite_state_machine 4 4 1 1 4->1 0 5 5 15 15 5->15 0 2 2 5->2 1 7 7 6 6 7->6 0 3 3 7->3 1 8 8 12 12 8->12 0 9 9 8->9 1 10 10 10->4 1 10->5 0 11 11 11->7 1 11->8 0 13 13 13->10 1 13->11 0 14 14 14->13 1 14->14 0 0 0 secret_node->0 0->4 1 0->0 1 0->1 0 1->15 0 1->2 1 15->12 0 15->9 1 2->6 0 2->3 1 6->7 1 6->8 0 3->4 1 3->5 0 12->13 1 12->14 0 9->10 1 9->11 0
NFA
Regular Expression
$(0+1)^*0(0+1)(0+1)(0+1)$
Grammar
$S \rightarrow aS | bS | aA | bA$ $A \rightarrow aB | bB$ $B \rightarrow aC | bC$ $C \rightarrow 0$
Each string contains 4 zero's
DFA
finite_state_machine
4
4
4->4
0,1
0
0
secret_node->0
0->0
1
1
1
0->1
0
1->1
1
2
2
1->2
0
2->2
1
3
3
2->3
0
3->4
0
3->3
1
NFA
Regular Expression
$(0+1)^*0(0+1)^*0(0+1)^*0(0+1)^*0(0+1)^*$
Grammar
$S \rightarrow aS | A$ $A \rightarrow 0B$ $B \rightarrow aB | 0C$ $C \rightarrow aC | 0D$ $D \rightarrow aD | 0E$ $E \rightarrow aE | \lambda$
At most 4 zero's
DFA
finite_state_machine
0
0
0->0
1
2
2
0->2
0
1
1
1->1
1
5
5
1->5
0
2->2
1
3
3
2->3
0
3->3
1
4
4
3->4
0
4->1
0
4->4
1
secret_node->0
5->5
1,0
NFA
Regular Expression
$1^*+1^*01^* + 1^*01^*01^* + 1^*01^*01^*01^* + 1^*01^*01^*01^*01^*$
Grammar
$S \rightarrow 1S | A \\ A \rightarrow A0B | \lambda \\ B \rightarrow 1B | C \\ C \rightarrow C0D | \lambda \\ D \rightarrow 1D | E \\ E \rightarrow E0F | \lambda \\F \rightarrow 1F | \lambda $
At least 2 zero's
DFA
finite_state_machine
2
2
2->2
0,1
0
0
secret_node->0
0->0
1
1
1
0->1
0
1->2
0
1->1
1
NFA
Regular Expression
$(0+1)^*0(0+1)^*0(0+1)^*$
Grammar
Emptiness Problem
Explanation of Emptiness Problem with DFA
DFA
0
1
2
1
1
0
0
1
0
Non Empty Problem
Explanation of Non-Empty Problem with DFA
DFA
1
2
3
4
0
a
a
b
b
a
b
b
b
a
a
Infinite Language
Explanation of Infinite Language with DFA
DFA
0
1
2
3
a
a
a
a
b
ε
Finite Language
Explanation of Finite Language with DFA
DFA
0
1
2
3
4
a
a
ε
a,b
a,b
b
b
Equivalance Problem
Explanation of Equivalance problem with DFA
DFA
0
1
2
1
0
0
1
0
Membership Problem
Explanation of Membership Problem with DFA
DFA
A
B
1
0
1
0
Ambiguity Problem
Explanation of Ambiguity Problem with DFA
CFG - Context Free Grammar
$S \rightarrow aSS | bSaS | \epsilon$
Inherent Ambiguous CFL - Context Free Language
L = {an bm ck where n = m (or) m = k}
$S \rightarrow S1 | S2$ $S1 \rightarrow AB$ $A \rightarrow aAb | ab$ $B \rightarrow cB | c$ $S2 \rightarrow Cb$ $C \rightarrow aC | a$ $D \rightarrow bDc | bc$
Simplification of CFG
Explanation of Simplification of CFG
Useless Symbol
$S \rightarrow AB$ $A \rightarrow a | B$ $B \rightarrow b | C$ $C \rightarrow aD | bC$ $D \rightarrow bC | aD$ $E \rightarrow a$
In the above example E -> a is useless and so should be removed.
Unit Production
$S \rightarrow AB$ $A \rightarrow a$ $B \rightarrow C | b$ $C \rightarrow D$ $D \rightarrow F$ $F \rightarrow a$
This will be changed to:
$S \rightarrow AB$ $A \rightarrow a$ $B \rightarrow a | b$$
Null Production
$S \rightarrow AaB$ $A \rightarrow a | \epsilon$ $B \rightarrow b | \epsilon$
This will be changed to:
$S \rightarrow AaB | aB | Aa | a$ $A \rightarrow a$ $B \rightarrow b$
NFA to DFA Conversion - Example 1
Conversion of NFA to DFA
Given NFA
0 1 a,b a b a
Converted DFA
0 1 2 b a b a b a
NFA to DFA Conversion - Example 2
Conversion of NFA to DFA
Given NFA
b b b b a a
Converted DFA
A C D B E a,b a a b b b a b a ε
$\epsilon$-NFA to NFA Conversion - Example 1
Conversion of $\epsilon$-NFA to NFA
$\epsilon$-NFA
q₀ q₁ q₂ 2 1 ε ε ε 0
NFA
q₀ q₁ q₂ 2 1,2 0,1 ε 0 1 0,1,2
$\epsilon$-NFA to NFA Conversion - Example 2
Conversion of $\epsilon$-NFA to NFA
$\epsilon$-NFA
q₀ q₁ q₂ q₃ 0 0 ε ε 0 1
NFA
q₀ q₂ q₃ q₁ 0 1 0 0 0 1 0 0 0 ε
Minimal DFA - Example 1
Minimization of DFA
Given DFA
q₀ q₁ q₃ q₂ q₄ a a b b b a a b a ε b
Steps to minify the DFA
Remove the unreachable states
Remove the dead states
Remove the equivalent states
Minified DFA
A B D C a a a b b a ε b b
Minimal DFA - Example 2
Minimization of DFA
Given DFA
A B C D E F G 1 0 0 0 1 1 0 1 0 1 0 1 0,1 ε
Steps to minify the DFA
Remove the unreachable states
Remove the dead states
Remove the equivalent states
Minified DFA
q₀ q₁ q₂ 0,1 1 0 0 1
RegEx from DFA - Example 1
Regular Expression to DFA
Given DFA
0 1 2 a,b b a,b a ε
Regular Expression
$(aa+bb)(a+b)*(a+b+c)$
Moorey Machine
Creation of Moorey Machine based on cases.
Construct a Moorey machine that takes all binary input and gives output as modulo 3
q₀ | 0 q₁ | 1 q₂ | 2 1 0 1 1 0 0 ε
Construct a Moorey machine that takes all string of a and b as input and counts the total number of ab
string present in a input string
q₀ | 0 q₁ | 0 q₂ | 1 b a b a ε a b
Construct a Moorey machine that accepts all binary string as input and outputs as
A if string is 1, 0
B if string is 1, 1
C for rest of cases
q₀ | C q₂ | C q₃ | B q₄ | A 0 1 1 0 1 0 1 ε 0
Meelay Machine
Creation of Meelay Machine based on cases
Construct a Meelay machine that accepts 1's compliment of a binary string
q₀ ε 1 | 0 0 | 1
Construct a Meelay machine that takes odd strings of a and b as input and produce 1 as output if last 2 symbols are same.
q₀ q₁ q₂ b | 0 a | 0 b | 0 b | 1 a | 1 a | 0 ε
Construct a Meelay machine which outputs 1 if last 2 symbols are different or else it outputs 0
q₀ q₁ q₂ b | 0 a | 1 b | 1 b | 0 a | 0 a | 0 ε
Moore to Meelay Machine
Conversion from Moore to Meelay Machine
Given Moorey Machine
q₀ | 1 q₂ | 3 q₁ | 2 b a a b a b ε
Converted Meelay Machine
q₀ q₂ q₁ b | 3 a | 2 a | 1 b | 3 a | 2 b | 1 ε
Moore to Meelay Machine
Conversion of Moore to Meelay Machine
Given Meelay Machine
q₀ q₁ q₂ b | 0 a | 0 a | 0 b | 0 ε b | 1 a | 1
Converted Moorey Machine
q₀ q₁ | 0 q₁₁ | 1 q₂ | 0 q₂₁ | 1 b a b a b a b a a b ε
Grammar Miscellaneous Cases
Cases of Grammar
b*a
$S \rightarrow aA$ $A \rightarrow \lambda | bA$
an bm where n $\geq$ 0 and m > 0
$S \rightarrow A | B$ $A \rightarrow aA | \lambda$ $B \rightarrow b | bB$
an bm where n > 0 or m > 0
$S \rightarrow aA | bB$ $A \rightarrow a | aA | B$ $B \rightarrow b | bB$
Number of a divisible by 3
$S \rightarrow \lambda | bB | AS$ $A \rightarrow Ba Ba Ba B$ $B \rightarrow bB | \lambda$
an bn cm where n, m $\geq$ 1
$S \rightarrow AB$ $A \rightarrow ab | aAb$ $B \rightarrow cB | c$
an bn cm dm where n, m $\geq$ 1
$S \rightarrow AB$ $A \rightarrow ab | aAb$ $B \rightarrow cBd | cd$
an bm cm dn where n, m $\geq$ 1
$S \rightarrow aSd | aAd$ $A \rightarrow bAc | bc$
an bm where n > m and n,m $\geq$ 1
$S \rightarrow aSb | aAb$ $A \rightarrow aAb | aA | a$
FA to Grammar
Conversion of FA to Grammar
Given DFA
S A b a b a ε
$S \rightarrow aS | bA | b$ $A \rightarrow bA | aS | b$
Given DFA
B C A D b a a b a b a,b
$A \rightarrow aB | bC$ $B \rightarrow aC | bD | b$ $C \rightarrow aD | bB | a$ $D \rightarrow aD | bD | a | b$
Grammer to FA
Conversion of Grammar to FA
Given Grammer
$S \rightarrow aB$ $B \rightarrow aB | b$ $C \rightarrow aC | b$
S B 2 C a a b a b
Context Free Grammar
Cases of Context Free Grammar
CFG that generates odd length palindrome
$S \rightarrow aSa | bSb |a | b$
CFG that generates even length palindrome
$S \rightarrow aSa | bSb | \lambda$
CFG that generates all palindrome
$S \rightarrow aSa | bSb | \lambda | a | b $
CFG that generates all English Language Palindrome
$S \rightarrow a | b | c .... | z | aSa | bSb | ... | zSz $
Practice Questions
Strings that start and end with the same symbol (using {a, b}).
Strings that start and end with different symbols (using {a, b}).
Strings containing an even number of a specific symbol ('a').
Strings with exactly one occurrence of a specific substring ('ab').
Strings that do not contain a specific substring (avoiding 'ab').
Strings where the nth symbol is a specific character (e.g., the third symbol is 'a').
Strings with an odd number of occurrences of two specific symbols ('a' and 'b').
Strings that start with a specific prefix ('ab').
Strings that end with a specific suffix ('ab').
Strings with at least n occurrences of a specific symbol (at least 2 'a's).
Strings representing binary numbers divisible by a specific number (using {0, 1}, e.g., divisible by 3).
Strings containing a number of symbols that is a prime number.
Strings where every occurrence of a specific symbol is immediately followed by another specific symbol (every 'a' is followed by 'b').
Strings with a length that is a multiple of a specific number (multiple of 4).
Strings that are palindromes (the same read forwards and backwards, using {a, b}).
Strings where the total number of two specific symbols is equal (the number of 'a's equals the number of 'b's).
Strings with a specific symbol appearing in every odd position ('a' appears in all odd positions).
Strings with alternating symbols from two specific sets (alternating between '0's and '1's).
Strings that are repetitions of a specific substring ('ababab').
Strings containing at least one occurrence of each symbol from a specific set (at least one 'a', one 'b').
Strings where every symbol occurs an even number of times.
Strings where every symbol occurs an odd number of times.
Strings with no consecutive occurrences of the same symbol (e.g., 'abab').
Strings with a palindrome at its center (e.g., 'aba').
Strings where the first half is a mirror image of the second half (e.g., 'abba').
Strings that are lexicographically ordered (using 'a', 'b').
Strings that contain exactly two different symbols ('a' and 'b').
Strings with exactly n pairs of consecutive symbols ('aa' or 'bb').
Strings that alternate between two specific symbols ('ababab').
Strings where a specific symbol never appears twice in a row (no 'aa' or 'bb' in the string).
Strings that contain a specific symbol in every even position.
Strings with a specific number of substrings equal to a given substring (three substrings equal to 'ab').
Strings where the difference in the number of two specific symbols is a specific value (the number of 'a's minus the number of 'b's equals 2).
Strings that contain a square number of symbols (4, 9, 16 symbols).
Strings where the sum of the ASCII values of all symbols is even.
Strings where the sum of the ASCII values of all symbols is odd.
Strings with a specific symbol appearing in all positions that are multiples of a given number ('a' appears in positions that are multiples of 3).
Strings that are the reverse of a given string ('ba' is the reverse of 'ab').
Strings with all symbols unique (no symbol is repeated).
Strings where each symbol is numerically greater than the preceding symbol (considering ASCII values, 'ab').
Strings where the concatenation of two specific symbols appears an even number of times ('abab' has 'ab' appearing twice).
Strings with a specific number of vowels (using 'a', considering 'a' as a vowel).
Strings with a specific number of consonants (using 'b', considering 'b' as a consonant).
Strings that contain only letters and no digits (using 'a', 'b').
Strings that contain only digits and no letters (using binary representation with '0', '1').
Strings that form a symmetric pattern (e.g., 'abba' or 'baab').
Strings with an equal number of 'a's and 'b's in every prefix.
Strings where no three consecutive symbols are the same (e.g., no 'aaa' or 'bbb').
Strings that represent valid binary sequences with alternating blocks of '0's and '1's (e.g., '01', '0011').
Strings with a balance of 'a's and 'b's (each 'a' can be paired with a 'b' in any order).
Strings where the sequence of 'a's is always followed by a longer sequence of 'b's (e.g., 'aabbb').
Strings that include at least one 'a' between every two 'b's.
Strings with non-overlapping, repeating substrings (e.g., 'abab' but not 'aba').
Strings that encode a sequence of balanced parentheses using 'a' for '(' and 'b' for ')'.
Strings where the occurrence of 'a's before any 'b' is always greater than or equal to the number of 'b's afterwards.
Strings that can be divided into two parts with equal numbers of 'a's and 'b's.
Strings where 'a' appears at least twice as often as 'b'.
Strings that do not start with 'bb'.
Strings where the last symbol is repeated at least once before the last position (e.g., 'abba').
Strings that include exactly one block of consecutive 'a's (e.g., 'baaab').
Strings that alternate between single 'a's and blocks of 'b's (e.g., 'abbbab').
Strings with triplets separated by 'a' (e.g., 'bbabbabba').
Strings that start with 'a' and end with 'b' without 'bb' in between.
Strings with exactly two 'a's separated by any number of 'b's (e.g., 'abba').
Strings where every 'b' is immediately followed by at least two 'a's (e.g., 'bbaa').
Strings where each 'a' is immediately preceded by a 'b' and followed by a 'b' (e.g., 'babb').
Strings with an increasing number of 'a's between 'b's (e.g., 'babbaabbb').
Strings that are composed of any combination of 'ab' or 'ba' substrings (e.g., 'abbaab').
Strings where the first 'a' appears before any 'b' (if 'a' is present).
Strings with a decreasing number of 'b's between 'a's (e.g., 'abbaba').
Strings that contain pairs of 'a's and 'b's in alternating order without overlap (e.g., 'abba').
Strings where 'b's are always in groups of even numbers (e.g., 'aabbbbaa' is not allowed).
Strings that do not end with the substring 'aba'.
Strings where 'a' and 'b' appear in groups, with 'a's always in odd and 'b's in even numbers (e.g., 'aaabbb').
Strings without an adjacent pair of 'a's following an adjacent pair of 'b's (e.g., 'bbaa' is not allowed).
Strings where every 'a' is surrounded by 'b's, but not every 'b' is surrounded by 'a's (e.g., 'bab' is allowed, but 'aba' is not).
Strings with a palindrome center and 'a' on both ends (e.g., 'abba').
Strings where the number of 'a's is a Fibonacci number.
Strings that include an even number of 'a's and an odd number of 'b's.
Strings where the number of 'b's never exceeds the number of 'a's at any point in the string.
Strings with an equal number of 'ab' and 'ba' substrings.
Strings that contain 'aba' as a substring, but not at the beginning or end.
Strings where the number of 'a's is twice the number of 'b's (e.g., 'aab').
Strings with 'b's distributed evenly among 'a's (e.g., 'abab').
Strings where 'a' occurs in multiples of three, and 'b' in multiples of two (e.g., 'aaabbb').
Strings where the sequence 'ab' is mirrored by 'ba' (e.g., 'abba').
Strings with a 'b' at both the beginning and end, enclosing a sequence of 'a's (e.g., 'baaab').
Strings where every 'b' is followed by a triple 'a' sequence (e.g., 'baaa').
Strings that exclude the sequence 'bbb' entirely.
Strings where 'a's and 'b's are in separate clusters, with 'a's always before 'b's (e.g., 'aaabbb').
Strings with a single 'a' surrounded by an equal number of 'b's on each side (e.g., 'bbabb').
Strings that contain exactly two 'b's with all 'a's at either end (e.g., 'aabaa').
Strings that alternate between clusters of 'a's and single 'b's (e.g., 'aababaa').
Strings with the first and last symbols being 'b', and all 'a's located in the middle (e.g., 'baaab').
Strings where the pattern 'ab' repeats an odd number of times (e.g., 'ababab').
Strings where 'a' appears only in even positions and 'b' appears only in odd positions (e.g., 'baba').
Strings that start with two 'a's followed by any number of 'b's (e.g., 'aabbbb').
Strings where the middle symbol is 'a', flanked by an equal number of 'b's on both sides (e.g., 'bbabb').
Strings with exactly three 'b's separated by at least one 'a' (e.g., 'babab').
Strings that form a repeating pattern of 'ab' ending with a single 'a' (e.g., 'ababa').