Give a contextfree grammar that generates language 10 10 03n

Give a context-free grammar that generates language (1+0)* 10. {0^3n 1^2n 0^m 1^m: n greaterthanorequalto 1, m greaterthanorequalto 1}.

Solution

(a)

The language is (1+0)*10

This represents all strings which end with 10. There can be any combination of 0’s and 1’s before the final 10.

So, consider the following context free grammar:

S -> A10

A -> 0A

A -> 1A

A -> epsilon

In the above grammar, the string generation starts with production rule S. So, string always terminates with 10.

The ‘A’ can introduce any combination of 0’s and 1’s at the beginning of the string. So, this grammar satisfies the given language.

Notice that every grammar whose production rules have a single non-terminal on the left side and any combination of terminals and non-terminals on the right side are context free grammars. So, the above grammar is context free.

------------------------------------------------------------------------------------------------------------

(b)

The language is 0³ⁿ1²ⁿ0^m1^m for n>=1 and m>=1

Since m and n are unrelated to each other. So, break down the language as concatenation of 0³ⁿ1²ⁿ and 0^m1^m

------------------------------------------------------------------------------------------------------------

First consider 0³ⁿ1²ⁿ for n >=1

Observe that for every three 0’s at the start, there are two 1’s following it.

So,

P -> 000 Q 11

Q -> P

Q -> epsilon

------------------------------------------------------------------------------------------------------------

Now consider 0^m1^m for m >=1

Observe that for every 0, there is a 1 at the end.

So,

R -> 0T1

T -> R

T -> epsilon

------------------------------------------------------------------------------------------------------------

Our required language is the concatenation of both.

So,

S -> PR

P -> 000 Q 11

Q -> P

Q -> epsilon

R -> 0T1

T -> R

T -> epsilon

The above is the required Context free grammar.

------------------------------------------------------------------------------------------------------------

I’ve given the context free grammars along with precise explanations for you to understand exactly how they are created. If you have any queries, please ask in the comments. I will make sure to help you with it.