CFG of Language contains at least three 1’s or three a’s {w | w contains at least three 1’s}

CFG of Language containing at least three 1’s or three a’s {w | w contains at least three 1’s}CFG of Language contains at least three 1’s or three a's {w | w contains at least three 1’s}

Context-free grammar for the language of all those strings containing at least 3three 1’s or three a’s having only one letter is mentioned below;

L ={w | w contains at least three 1’s and starting with 111}

S → X1X1X1X
X→ 0X | 1X | ε

L ={w | w contains at least three 0’s and starting with 000}

S → X0X0X0X
X → 0X | 1X | ε

L ={w | w contains at least three a’s and starting with aaa}

S → XaXaXaX
X → aX | bX | ε

L ={w | w contains at least three b’s and starting with bbb}

S → XbXbXbX
X → aX | bX | ε

Now we can read any kind of odd length string.

Examples of CFG of strings containining at least three 1’s and starting with 000.

To read 111;

CFG:

S → X1X1X1X
X → 0X | 1X | ε

Path to Read the String

S → X1X1X1X   //Read first 111.

X⇒ε  //Read 111ε.

finally, we can read it as 111.

Congratulation, the string can be read and the machine can be stoped after successfully completing its task.

To read 1110;

CFG:

S → X1X1X1X
X → 0X | 1X | ε

Path to Read the String

S → X1X1X1X   //Read first 111.

X → 0X //Read 1110.

X⇒ε  //Read 1110ε.

finally, we can read it as 1110.

Congratulation, the string can be read and the machine can be stoped after successfully completing its task.

To read 110;

CFG:

S → X1X1X1X
X → 0X | 1X | ε

Path to Read the String

S → X1X1X1X   //Read first 11 and after that machine will read 1, not o. So this string cant is accepted by this CFG.

Oh sorry, the string cant be accepted by this CFG, because this string is not part of the assigned language.


More Examples of CFG

  1. Intro to Context Free Grammar with 12 Examples
  2. CFG of Language of all even and odd length palindromes
  3. Context Free Grammar CFG for language of all even length strings
  4. CFG for the language of all non Palindromes
  5. CFG for strings with unequal numbers of a and b
  6. CFG of odd Length strings {w | the length of w is odd}
  7. CFG of Language contains at least three 1’s or three a’s {w | w contains at least three 1’s}
  8. CFG for the language L = 0n1n where n>=1
  9. CFG for the language L = 0n12n where n>=1
  10. Write a CFG for the language L = 0n14n where n>=1
  11. CFG for {an b an+1 | n >=0}
  12. CFG for {an b an+2 | n >=0}
  13. CFG for {an b an+3 | n >=0}

Add a Comment