DFA, NFA, RE, Grammar Cases - CSU360 - Shoolini U

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_machine000->0a,bsecret_node->0

NFA

finite_state_machine000->0a,bsecret_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_machine111->1a,b00secret_node->00->1a,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ε111->1a,b00secret_node->00->1a220->2b2->2a,b

NFA

01aa,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_machine111->1b00secret_node->00->1b0->1a0->0a

NFA

01ba,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_machine111->1b221->2a00secret_node->00->2a330->3b2->1b2->2a3->3a,b

NFA

012abaa,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_machine222->2b112->1a333->3a,b00secret_node->00->2b0->3a1->2b1->1a

NFA

01a,ba,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

01234bbbba,baaaaε

NFA

0123bbb

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_machine333->3a,b00secret_node->00->0a110->1b0->1a220->2a1->2b2->3b

NFA

0123bbbb

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_machine11551->5a,b00secret_node->0440->4a,b334->3a,b222->1a,b3->2a,b5->5a,b

NFA

01235a,ba,ba,ba.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_machine444->4a,b00secret_node->00->0a110->1b0->1a220->2a330->3a1->2b2->3b3->4b

NFA

01235bbbbb

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_machine00220->2a,b11551->5a,b332->3a,b443->4a,b4->1a,bsecret_node->05->5a,b

NFA

01235a,ba,ba,ba.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_machine00220->2b110->1a0->1asecret_node->02->2b2->1a1->1b

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_machine00110->10,10->10,1secret_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_machine00330->30,1110->10,1secret_node->0223->20,12->10,1

NFA

Regular Expression

$((0+1)(0+1)(0+1)(0+1))^*$

Grammar

Number of b is odd

DFA

finite_state_machine111->1a00secret_node->00->1b0->1b0->0a

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_machine1100secret_node->00->1a,b0->1a,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_machine00220->2a,b110->1a,bsecret_node->02->1a,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_machine222->2b332->3a444->4a114->1b00secret_node->00->3a0->1b3->4a3->1b1->2b1->3a

NFA

0123bbaaa,b

Regular Expression

$(a+b)^*(aa+bb)$

Grammar

$S \rightarrow aS | bS | aa | bb$

First 2 symbols are same

DFA

finite_state_machine111->1a,b00secret_node->0330->3a220->2b3->1a443->4b2->1b2->4a4->4a,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_machine22332->3b442->4a3->2a113->1b00secret_node->00->4a0->1b4->3b4->4a1->2a1->1b

NFA

0123baaba,b

Regular Expression

$(a+b)^*(ab+ba)$

Grammar

$S \rightarrow aS | bS | ab | ba$

Start and end with same symbol

DFA

finite_state_machine111->1b221->2a444->4a334->3b00secret_node->00->1b0->4a2->1b2->2a3->4a3->3b

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 0s odd

DFA

finite_state_machine11221->20441->4100secret_node->0330->310->310->403->102->102->414->41,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_machine11221->20,100secret_node->00->100->212->10,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_machine333->30,100secret_node->00->01110->100->11221->202->312->20

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_machine333->30,100secret_node->0440->40110->114->11554->501->40221->212->312->405->305->11

NFA

012345111000

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_machine111->1a,b00secret_node->0330->3a,b223->2a,b2->1a442->4b4->4a,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 | aab,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 | aab,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 | aab,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 | aab,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 | aab,a | εb,a | εε,a | εε,a | εε,Z₀ | ε

L = { an bm | n,m >=0}

DFA

finite_state_machine000->0a110->1b1->1b221->2asecret_node->02->2a,b

NFA

$\epsilon$-NFA

baε

Regular Expression

$a^*b^*$

Grammar

$S \rightarrow aS | bS | \lambda$

L = { an bm cp dk| n,m,p,k >=0}

$\epsilon$-NFA

0123εεεεdcba

Accept all substring of n length string W

$\epsilon$-NFA

0123abcεεεεε

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_machine33113->1000secret_node->00->310->010->101->10221->212->312->10

NFA

01230110,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

012bbbaaaε

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_machine111->10,100secret_node->0440->40,1334->30,1222->10552->513->20,15->50,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_machine44114->105515155->150225->2177667->60337->318812128->120998->91101010->4110->50111111->7111->80131313->10113->110141414->13114->14000secret_node->00->410->010->101->1501->2115->12015->912->602->316->716->803->413->5012->13112->1409->1019->110

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

01a,baba

Converted DFA

012bababa

NFA to DFA Conversion - Example 2

Conversion of NFA to DFA

Given NFA

bbbbaa

Converted DFA

ACDBEa,baabbbabaε

$\epsilon$-NFA to NFA Conversion - Example 1

Conversion of $\epsilon$-NFA to NFA

$\epsilon$-NFA

q₀q₁q₂21εεε0

NFA

q₀q₁q₂21,20,1ε010,1,2

$\epsilon$-NFA to NFA Conversion - Example 2

Conversion of $\epsilon$-NFA to NFA

$\epsilon$-NFA

q₀q₁q₂q₃00εε01

NFA

q₀q₂q₃q₁010001000ε

Minimal DFA - Example 1

Minimization of DFA

Given DFA

q₀q₁q₃q₂q₄aabbbaabaεb

Steps to minify the DFA

  1. Remove the unreachable states
  2. Remove the dead states
  3. Remove the equivalent states

Minified DFA

ABDCaaabbaεbb

Minimal DFA - Example 2

Minimization of DFA

Given DFA

ABCDEFG1000110101010,1ε

Steps to minify the DFA

  1. Remove the unreachable states
  2. Remove the dead states
  3. Remove the equivalent states

Minified DFA

q₀q₁q₂0,11001

RegEx from DFA - Example 1

Regular Expression to DFA

Given DFA

012a,bba,baε

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₀ | 0q₁ | 1q₂ | 2101100ε

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₀ | 0q₁ | 0q₂ | 1babaεab

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₀ | Cq₂ | Cq₃ | Bq₄ | A0110101ε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 | 00 | 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 | 0a | 0b | 0b | 1a | 1a | 0ε

Construct a Meelay machine which outputs 1 if last 2 symbols are different or else it outputs 0

q₀q₁q₂b | 0a | 1b | 1b | 0a | 0a | 0ε

Moore to Meelay Machine

Conversion from Moore to Meelay Machine

Given Moorey Machine

q₀ | 1q₂ | 3q₁ | 2baababε

Converted Meelay Machine

q₀q₂q₁b | 3a | 2a | 1b | 3a | 2b | 1ε

Moore to Meelay Machine

Conversion of Moore to Meelay Machine

Given Meelay Machine

q₀q₁q₂b | 0a | 0a | 0b | 0εb | 1a | 1

Converted Moorey Machine

q₀q₁ | 0q₁₁ | 1q₂ | 0q₂₁ | 1babababaabε

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

SAbabaε

$S \rightarrow aS | bA | b$
$A \rightarrow bA | aS | b$

Given DFA

BCADbaababa,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$

SB2Caabab

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

  1. Strings that start and end with the same symbol (using {a, b}).
  2. Strings that start and end with different symbols (using {a, b}).
  3. Strings containing an even number of a specific symbol ('a').
  4. Strings with exactly one occurrence of a specific substring ('ab').
  5. Strings that do not contain a specific substring (avoiding 'ab').
  6. Strings where the nth symbol is a specific character (e.g., the third symbol is 'a').
  7. Strings with an odd number of occurrences of two specific symbols ('a' and 'b').
  8. Strings that start with a specific prefix ('ab').
  9. Strings that end with a specific suffix ('ab').
  10. Strings with at least n occurrences of a specific symbol (at least 2 'a's).
  11. Strings representing binary numbers divisible by a specific number (using {0, 1}, e.g., divisible by 3).
  12. Strings containing a number of symbols that is a prime number.
  13. Strings where every occurrence of a specific symbol is immediately followed by another specific symbol (every 'a' is followed by 'b').
  14. Strings with a length that is a multiple of a specific number (multiple of 4).
  15. Strings that are palindromes (the same read forwards and backwards, using {a, b}).
  16. Strings where the total number of two specific symbols is equal (the number of 'a's equals the number of 'b's).
  17. Strings with a specific symbol appearing in every odd position ('a' appears in all odd positions).
  18. Strings with alternating symbols from two specific sets (alternating between '0's and '1's).
  19. Strings that are repetitions of a specific substring ('ababab').
  20. Strings containing at least one occurrence of each symbol from a specific set (at least one 'a', one 'b').
  21. Strings where every symbol occurs an even number of times.
  22. Strings where every symbol occurs an odd number of times.
  23. Strings with no consecutive occurrences of the same symbol (e.g., 'abab').
  24. Strings with a palindrome at its center (e.g., 'aba').
  25. Strings where the first half is a mirror image of the second half (e.g., 'abba').
  26. Strings that are lexicographically ordered (using 'a', 'b').
  27. Strings that contain exactly two different symbols ('a' and 'b').
  28. Strings with exactly n pairs of consecutive symbols ('aa' or 'bb').
  29. Strings that alternate between two specific symbols ('ababab').
  30. Strings where a specific symbol never appears twice in a row (no 'aa' or 'bb' in the string).
  31. Strings that contain a specific symbol in every even position.
  32. Strings with a specific number of substrings equal to a given substring (three substrings equal to 'ab').
  33. 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).
  34. Strings that contain a square number of symbols (4, 9, 16 symbols).
  35. Strings where the sum of the ASCII values of all symbols is even.
  36. Strings where the sum of the ASCII values of all symbols is odd.
  37. 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).
  38. Strings that are the reverse of a given string ('ba' is the reverse of 'ab').
  39. Strings with all symbols unique (no symbol is repeated).
  40. Strings where each symbol is numerically greater than the preceding symbol (considering ASCII values, 'ab').
  41. Strings where the concatenation of two specific symbols appears an even number of times ('abab' has 'ab' appearing twice).
  42. Strings with a specific number of vowels (using 'a', considering 'a' as a vowel).
  43. Strings with a specific number of consonants (using 'b', considering 'b' as a consonant).
  44. Strings that contain only letters and no digits (using 'a', 'b').
  45. Strings that contain only digits and no letters (using binary representation with '0', '1').
  46. Strings that form a symmetric pattern (e.g., 'abba' or 'baab').
  47. Strings with an equal number of 'a's and 'b's in every prefix.
  48. Strings where no three consecutive symbols are the same (e.g., no 'aaa' or 'bbb').
  49. Strings that represent valid binary sequences with alternating blocks of '0's and '1's (e.g., '01', '0011').
  50. Strings with a balance of 'a's and 'b's (each 'a' can be paired with a 'b' in any order).
  51. Strings where the sequence of 'a's is always followed by a longer sequence of 'b's (e.g., 'aabbb').
  52. Strings that include at least one 'a' between every two 'b's.
  53. Strings with non-overlapping, repeating substrings (e.g., 'abab' but not 'aba').
  54. Strings that encode a sequence of balanced parentheses using 'a' for '(' and 'b' for ')'.
  55. Strings where the occurrence of 'a's before any 'b' is always greater than or equal to the number of 'b's afterwards.
  56. Strings that can be divided into two parts with equal numbers of 'a's and 'b's.
  57. Strings where 'a' appears at least twice as often as 'b'.
  58. Strings that do not start with 'bb'.
  59. Strings where the last symbol is repeated at least once before the last position (e.g., 'abba').
  60. Strings that include exactly one block of consecutive 'a's (e.g., 'baaab').
  61. Strings that alternate between single 'a's and blocks of 'b's (e.g., 'abbbab').
  62. Strings with triplets separated by 'a' (e.g., 'bbabbabba').
  63. Strings that start with 'a' and end with 'b' without 'bb' in between.
  64. Strings with exactly two 'a's separated by any number of 'b's (e.g., 'abba').
  65. Strings where every 'b' is immediately followed by at least two 'a's (e.g., 'bbaa').
  66. Strings where each 'a' is immediately preceded by a 'b' and followed by a 'b' (e.g., 'babb').
  67. Strings with an increasing number of 'a's between 'b's (e.g., 'babbaabbb').
  68. Strings that are composed of any combination of 'ab' or 'ba' substrings (e.g., 'abbaab').
  69. Strings where the first 'a' appears before any 'b' (if 'a' is present).
  70. Strings with a decreasing number of 'b's between 'a's (e.g., 'abbaba').
  71. Strings that contain pairs of 'a's and 'b's in alternating order without overlap (e.g., 'abba').
  72. Strings where 'b's are always in groups of even numbers (e.g., 'aabbbbaa' is not allowed).
  73. Strings that do not end with the substring 'aba'.
  74. Strings where 'a' and 'b' appear in groups, with 'a's always in odd and 'b's in even numbers (e.g., 'aaabbb').
  75. Strings without an adjacent pair of 'a's following an adjacent pair of 'b's (e.g., 'bbaa' is not allowed).
  76. 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).
  77. Strings with a palindrome center and 'a' on both ends (e.g., 'abba').
  78. Strings where the number of 'a's is a Fibonacci number.
  79. Strings that include an even number of 'a's and an odd number of 'b's.
  80. Strings where the number of 'b's never exceeds the number of 'a's at any point in the string.
  81. Strings with an equal number of 'ab' and 'ba' substrings.
  82. Strings that contain 'aba' as a substring, but not at the beginning or end.
  83. Strings where the number of 'a's is twice the number of 'b's (e.g., 'aab').
  84. Strings with 'b's distributed evenly among 'a's (e.g., 'abab').
  85. Strings where 'a' occurs in multiples of three, and 'b' in multiples of two (e.g., 'aaabbb').
  86. Strings where the sequence 'ab' is mirrored by 'ba' (e.g., 'abba').
  87. Strings with a 'b' at both the beginning and end, enclosing a sequence of 'a's (e.g., 'baaab').
  88. Strings where every 'b' is followed by a triple 'a' sequence (e.g., 'baaa').
  89. Strings that exclude the sequence 'bbb' entirely.
  90. Strings where 'a's and 'b's are in separate clusters, with 'a's always before 'b's (e.g., 'aaabbb').
  91. Strings with a single 'a' surrounded by an equal number of 'b's on each side (e.g., 'bbabb').
  92. Strings that contain exactly two 'b's with all 'a's at either end (e.g., 'aabaa').
  93. Strings that alternate between clusters of 'a's and single 'b's (e.g., 'aababaa').
  94. Strings with the first and last symbols being 'b', and all 'a's located in the middle (e.g., 'baaab').
  95. Strings where the pattern 'ab' repeats an odd number of times (e.g., 'ababab').
  96. Strings where 'a' appears only in even positions and 'b' appears only in odd positions (e.g., 'baba').
  97. Strings that start with two 'a's followed by any number of 'b's (e.g., 'aabbbb').
  98. Strings where the middle symbol is 'a', flanked by an equal number of 'b's on both sides (e.g., 'bbabb').
  99. Strings with exactly three 'b's separated by at least one 'a' (e.g., 'babab').
  100. Strings that form a repeating pattern of 'ab' ending with a single 'a' (e.g., 'ababa').