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

By: Prof. Fazal Rehman Shamil | Whatsapp:+923028700085

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.