Question

Find a phrase-structure grammar for each of these languages.

a) the set of all bit strings containing an even number of 0s and no 1s

b) the set of all bit strings made up of a 1 followed by an odd number of 0s

c) the set of all bit strings containing an even number of 0s and an even number of 1s

d) the set of all strings containing 10 or more 0s and no 1s

e) the set of all strings containing more 0s than 1s

f) the set of all strings containing an equal number of 0s and 1s

g) the set of all strings containing an unequal number of 0s and 1s

Short answer

a) The phase structure grammar is \({\bf{S}} \to {\bf{00A and A}} \to {\bf{00A, A}} \to {\bf{\lambda }}\)

b) The phase structure grammar is\({\bf{S}} \to {\bf{10A and A}} \to {\bf{00A and A}} \to {\bf{\lambda }}\).

c) The phase structure grammar is:

\({\bf{S}} \to {\bf{AB and A}} \to {\bf{00A, A}} \to {\bf{\lambda , B}} \to {\bf{11B and B}} \to {\bf{\lambda }}\).

d) The phase structure grammar is\({\bf{S}} \to {\bf{0000000000A, A}} \to {\bf{0A, A}} \to {\bf{\lambda }}\).

e) The phase structure grammar is:

\({\bf{S}} \to {\bf{S0A, S}} \to {\bf{A0A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{\lambda }}\).

f) The phase structure grammar is:

\({\bf{S}} \to {\bf{S1A, S}} \to {\bf{A1A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{\lambda }}\).

g) The phase structure grammar is:

\({\bf{S}} \to {\bf{S0A, S}} \to {\bf{A0A, S}} \to {\bf{S1A, S}} \to {\bf{A1A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{\lambda }}\).

Step-by-step solution

about the language generated by the grammar.

Let \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) be a phrase-structure grammar. The language generated by G (or the language of G), denoted by L(G), and is the set of all strings of terminals that are derivable from the starting state S.

Now, we shall find a phrase-structure grammar for part (a) languages.

We can start with\({\bf{S}} \to {\bf{00A}}\)and\({\bf{A}} \to {\bf{00A, A}} \to {\bf{\lambda }}\).

So, the string starts with an even number of 0's and it will consist of only even numbers of 0's by the rule \({\bf{A}} \to {\bf{00A}}\) and no 1's.

Hence, the phrase structure grammar for the language is\({\bf{S}} \to {\bf{00A}}\) and\({\bf{A}} \to {\bf{00A, A}} \to {\bf{\lambda }}\).

Now, we shall find a phrase-structure grammar for part (b) languages.

We can start with\({\bf{S}} \to {\bf{10A}}\)and \({\bf{A}} \to {\bf{00A}}\)and\({\bf{A}} \to {\bf{\lambda }}\).

So, the production starts with a \({\bf{1(S}} \to {\bf{10 A)}}\) and continues with the odd number of 0s as the rule \({\bf{A}} \to {\bf{004a}}\) adds two Os to the end of the string 10.

Hence, the phrase structure grammar for the language is\({\bf{S}} \to {\bf{10A}}\)and\({\bf{A}} \to {\bf{00A}}\)and\({\bf{A}} \to {\bf{\lambda }}\).

Now, we shall find a phrase-structure grammar for part (c) languages.

We can start with\({\bf{S}} \to {\bf{AB}}\)and \({\bf{A}} \to {\bf{00A, A}} \to {\bf{\lambda , B}} \to {\bf{11B}}\)and\({\bf{B}} \to {\bf{\lambda }}\).

So, the string starts with even numbers of 0's and 1’s and it will consist of only even numbers of 0's and 1's.

Hence, the phrase structure grammar for the language is\({\bf{S}} \to {\bf{AB}}\)and\({\bf{A}} \to {\bf{00A, A}} \to {\bf{\lambda , B}} \to {\bf{11B}}\)and\({\bf{B}} \to {\bf{\lambda }}\).

Now, we shall find a phrase-structure grammar for part (d) languages.

We can start with\({\bf{S}} \to {\bf{0000000000A, A}} \to {\bf{0A, A}} \to {\bf{\lambda }}\).

So, the string starts with ten 0s and can stop by the rule \({\bf{A}} \to {\bf{\lambda }}\) or continue to add a 0 at a time by rule\({\bf{A}} \to {\bf{0A}}\).

Hence, the phrase structure grammar for the language is:

\({\bf{S}} \to {\bf{0000000000A, A}} \to {\bf{0A, A}} \to {\bf{\lambda }}\).

Now, we shall find a phrase-structure grammar for part (e) languages.

We can start with\({\bf{S}} \to {\bf{S0A, S}} \to {\bf{A0A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{\lambda }}\).

The productions for A will create strings that have an equal number of 0s and 1s.

The start symbol S will generate strings of the form A0A, A0A0A, ..., (A0) nA, that 0s in between strings that contain an equal number of 0s and 1s.

Thus, these strings have more 0s than 1s.

Hence, the phrase structure grammar for the language is:

\({\bf{S}} \to {\bf{S0A, S}} \to {\bf{A0A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{l}}\).

Now, we shall find a phrase-structure grammar for part (f) languages.

In part (e) we created a grammar for strings that have more Os than 1s.

The grammar was\({\bf{S}} \to {\bf{S0A, S}} \to {\bf{A0A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{\lambda }}\).

If we replace the 0s with 1s in the productions for S, in the grammar listed above, then it will generate strings that have more is than 0s.

The grammar will become\({\bf{S}} \to {\bf{S1A, S}} \to {\bf{A1A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{\lambda }}\).

Now, we shall find a phrase-structure grammar for part (g) languages.

There are two cases possible, which are there are more 1s than 0s or there are more 0s than 1s.

In part (e) we created a grammar for strings that have more 0s than 1s.

The grammar was\({\bf{S}} \to {\bf{S0A, S}} \to {\bf{A0A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{\lambda }}\).

In part (f) we created a grammar for strings that have more is than Os. The grammar was\({\bf{S}} \to {\bf{S1A, S}} \to {\bf{A1A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{\lambda }}\).

Merging these two grammars will give us the required grammar for strings in which the number of 1s is not equal to the number of 0s.

The grammar is given below:

\({\bf{S}} \to {\bf{S0A, S}} \to {\bf{A0A, S}} \to {\bf{S1A, S}} \to {\bf{A1A, A}} \to {\bf{1A0A, A}} \to {\bf{0A1A, A}} \to {\bf{\lambda }}\).