• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q1SE

Expert-verified
Found in: Page 901

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Find a phrase-structure grammar that generates each of these languages.$${\bf{a)}}$$ the set of bit strings of the form $${{\bf{0}}^{{\bf{2n}}}}{{\bf{1}}^{{\bf{3n}}}}$$, where $${\bf{n}}$$ is a nonnegative integer$${\bf{b)}}$$ the set of bit strings with twice as many $${\bf{0's}}$$ as $${\bf{1's}}$$$${\bf{c)}}$$ the set of bit strings of the form $${{\bf{w}}^{\bf{2}}}$$, where $${\bf{w}}$$ is a bit string

$${\bf{a)}}$$ The phase-structure grammar is $${\bf{G = (V,T,S,P),V = \{ S,0,1\} ,T = \{ 0,1\} ,S}} \to {\bf{00S111,S}} \to {\bf{\lambda }}$$

$${\bf{b)}}$$ The phase-structure grammar is $${\bf{G = (V,T,S,P),V = \{ S,A,B,0,1\} ,T = \{ 0,1\} ,S}} \to {\bf{AABS,S}} \to {\bf{\lambda ,AB}} \to {\bf{BA,BA}} \to {\bf{AB,A}} \to {\bf{0,B}} \to 1$$

$${\bf{c)}}$$ The phase-structure grammar is $$\begin{array}{c}{\bf{G = (V,T,S,P),V = \{ S,A,B,E,F,0,1\} ,T = \{ 0,1\} ,S}} \to {\bf{EF,F}} \to {\bf{0FA,F}} \to {\bf{1FB,F}} \to {\bf{\lambda ,0A}} \to {\bf{A0,}}\\{\bf{0B}} \to {\bf{B0,1A}} \to {\bf{A1,1B}} \to {\bf{B1,EA}} \to {\bf{E0,EB}} \to {\bf{E1,E}} \to {\bf{\lambda }}\end{array}$$

See the step by step solution

## Step 1: Definition

A language is a subset of the set of all possible strings over an alphabet.

Phase structure grammar $$\left( {{\bf{V,T,S,P}}} \right)$$ shows the description of a language, $${\bf{V}}$$ is the alphabet, $${\bf{T}}$$ is a set of terminal symbols, $${\bf{S}}$$ is the start symbol and $${\bf{P}}$$ is a set of productions.

## Step 2: Finding the phase-structure

(a)

It is given that $$\left\{ {{{\bf{0}}^{{\bf{2n}}}}{{\bf{1}}^{{\bf{3n}}}}\mid {\bf{n}} \ge 0} \right\}$$.

The terminal symbol set of all possible symbols in the resulting strings.

$${\bf{T = }}\left\{ {{\bf{0,1}}} \right\}$$

Let $${\bf{S}}$$ be the start state.

When $${\bf{n = 0}}$$, then the string $${{\bf{0}}^{{\bf{2n}}}}{{\bf{1}}^{{\bf{3n}}}}$$ is the empty string $${\bf{\lambda }}$$ and thus there needs to be a production step from $${\bf{S}}$$ to $${\bf{\lambda }}$$.

$${\bf{S}} \to 1$$

Strings of the form $${{\bf{0}}^{{\bf{2n}}}}{{\bf{1}}^{{\bf{3n}}}}$$ have an even number of $${\bf{0's}}$$ followed by a number of $${\bf{1's}}$$ that is divisible by $$1$$. The $${\bf{0's}}$$ thus have to occur in pairs $$00$$ and the $${\bf{1's}}$$ occur in triples $$111$$ (moreover, note that the number of pairs $$00$$ and the number of triples $$111$$ has to be the same, as they are both represented by the integer $${\bf{n}}$$ ).

Thus, any non-empty string is then of the form $${\bf{00 S 111}}$$, which implies that you require a production step from $${\bf{S}}$$ to $${\bf{00 S 111}}$$.

$${\bf{S}} \to {\bf{00S111}}$$

## Step 3: Combining all the answers

The alphabet $${\bf{V}}$$ contains all symbols used in the production steps above.

$${\bf{V = }}\left\{ {{\bf{S, 0,1}}} \right\}$$

Combining all this information.

Therefore, it gets the phase-structure grammar:

$${\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)$$

$${\bf{V = }}\left\{ {{\bf{S, 0,1}}} \right\}$$ Alphabet

$${\bf{T = }}\left\{ {{\bf{0,1}}} \right\}$$ Set of terminal symbols

$${\bf{S}}$$ Start symbol

Set of productions $${\bf{P}}$$

$$\begin{array}{l}{\bf{S}} \to {\bf{00S111}}\\{\bf{S}} \to {\bf{\lambda }}\end{array}$$

## Step 4: Finding the phase-structure

(b)

Set of bit strings with twice as many $${\bf{0's}}$$ as $${\bf{1's}}$$.

The set of terminal symbols of all possible symbols in the resulting strings.

$${\bf{T = }}\left\{ {{\bf{0,1}}} \right\}$$

Let $${\bf{S}}$$ be the start state.

Let $${\bf{A}}$$ represent the $${\bf{0's}}$$ and $${\bf{B}}$$ represents the $${\bf{1's}}$$.

$$\begin{array}{l}{\bf{A}} \to 0\\{\bf{B}} \to 1\end{array}$$

Since there are twice as many $${\bf{0's}}$$ as $${\bf{1's}}$$, a string needs to be of the form $${\bf{AABS}}$$ (where the $${\bf{A's}}$$ and $${\bf{B's}}$$ can occur in any sequence). Thus, it requires a production step from $${\bf{S}}$$ to $${\bf{AABS}}$$. It also require productions steps from $${\bf{AB}}$$ to $${\bf{BA}}$$ and from $${\bf{BA}}$$ to $${\bf{AB}}$$ (such that the order of the $${\bf{0's}}$$ and $${\bf{1's}}$$ can be changed).

$$\begin{array}{l}{\bf{S}} \to {\bf{AABS}}\\{\bf{AB}} \to {\bf{BA}}\\{\bf{BA}} \to {\bf{AB}}\end{array}$$

Finally, note that the empty string was not yet included (while the empty string has twice as many $${\bf{0's}}$$ as $${\bf{1's}}$$ and it doesn't have any $${\bf{0's}}$$ nor $${\bf{1's}}$$).

## Step 5: Combining all the answers

It needs to include the empty string $${\bf{\lambda }}$$ and thus you require a production step from $${\bf{S}}$$ to $${\bf{\lambda }}$$.

$${\bf{S}} \to {\bf{\lambda }}$$

The alphabet $${\bf{V}}$$ contains all symbols used in the production steps above.

$${\bf{V = }}\left\{ {{\bf{S, A, B, 0,1}}} \right\}$$

Combining all this information.

Therefore, it gets the phase-structure grammar:

$${\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)$$

$${\bf{V = }}\left\{ {{\bf{S, A, B, 0,1}}} \right\}$$Alphabet

$${\bf{T = }}\left\{ {{\bf{0,1}}} \right\}$$ Set of terminal symbols

$${\bf{S}}$$ Start symbol

$${\bf{S}}$$ Set of productions $${\bf{P}}$$

$$\begin{array}{l}{\bf{S}} \to {\bf{AABS}}\\{\bf{S}} \to {\bf{\lambda }}\\{\bf{AB}} \to {\bf{BA}}\\{\bf{BA}} \to {\bf{AB}}\\{\bf{A}} \to {\bf{0}}\\{\bf{B}} \to 1\end{array}$$

## Step 6: Finding the phase-structure

(c)

Let $$\left\{ {{{\bf{w}}^{\bf{2}}}\mid {\bf{w}}} \right\}$$ is some bit string.

The set of terminal symbols of all possible symbols in the resulting strings.

$${\bf{T = }}\left\{ {{\bf{0,1}}} \right\}$$

Let $${\bf{S}}$$ be the start state.

Let $${\bf{A}}$$ represent the $${\bf{0's}}$$ and $${\bf{B}}$$ represents the $${\bf{1's}}$$.

It will first generate all strings of the form $$\left\{ {{\bf{Ew}}\left( {{{\bf{w}}^{\bf{R}}}} \right)\mid {\bf{w}}} \right\}$$ is some bit string. If the string $${\bf{w}}\left( {{{\bf{w}}^{\bf{R}}}} \right)$$ starts with a $$0$$, then it also has to end with a $$0$$. If the string $${\bf{w}}\left( {{{\bf{w}}^{\bf{R}}}} \right)$$ starts with a $$1$$, then it also has to end with a $$1$$. Since It will still have the change the end of the string lateron (to rewrite it as $${{\bf{w}}^{\bf{2}}}$$), It will use $${\bf{A}}$$ and $${\bf{B}}$$ at the end of the string to represent the $${\bf{0's}}$$ and $${\bf{1's}}$$ (but not at the beginning).

$$\begin{array}{l}{\bf{S}} \to {\bf{EF}}\\{\bf{F}} \to {\bf{0FA}}\\{\bf{F}} \to {\bf{1FB}}\\{\bf{F}} \to {\bf{\lambda }}\end{array}$$

## Step 7: Finding the phase-structure

Next, it moves all symbols $${\bf{A}}$$ and $${\bf{B}}$$ to the front of the string, thus the string $${\bf{Ew}}\left( {{{\bf{w}}^{\bf{R}}}} \right)$$ becomes $${\bf{E}}\left( {{{\bf{w}}^{\bf{R}}}} \right){\bf{w}}$$.

$$\begin{array}{l}{\bf{0A}} \to {\bf{A0}}\\{\bf{0B}} \to {\bf{B0}}\end{array}$$

$$\begin{array}{l}{\bf{1A}} \to {\bf{A1}}\\{\bf{1B}} \to {\bf{B1}}\end{array}$$

Once the symbols occur right after $${\bf{E}}$$, it will replace the $${\bf{A}}$$ or $${\bf{B}}$$ by its value ($$0$$ or $$1$$ respectively). Then it will move the $$0$$ or $$1$$ to the middle of the string (by using the above production steps again $${\bf{0A}} \to {\bf{A0,0B}} \to {\bf{B0,1A}} \to {\bf{A1,1B}} \to {\bf{B1}}$$ ). Then repeating the procedure will result in the first half of the string to be returned in the opposite order (thus the string $${\bf{E}}\left( {{{\bf{w}}^{\bf{R}}}} \right){\bf{w}}$$ is replaced by $${\bf{Eww = E}}{{\bf{w}}^{\bf{2}}}$$).

$$\begin{array}{l}{\bf{EA}} \to {\bf{E0}}\\{\bf{EB}} \to {\bf{E1}}\end{array}$$

Finally, it still need to remove the symbol $${\bf{E}}$$ from the last string $${\bf{E}}{{\bf{w}}^{\bf{2}}}$$, which can be done by replacing $${\bf{E}}$$ by the empty string $${\bf{\lambda }}$$.

$${\bf{E}} \to {\bf{\lambda }}$$

The alphabet $${\bf{V}}$$ contains all symbols used in the production steps above.

$${\bf{V = }}\left\{ {{\bf{S, A, B, E, F, 0,1}}} \right\}$$

## Step 8: Combining all the answers

Combining all this information.

Therefore, it gets the phase-structure grammar:

$${\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)$$

$${\bf{V = }}\left\{ {{\bf{S, A, B, E, F, 0,1}}} \right\}$$ Alphabet

$${\bf{T = }}\left\{ {{\bf{0,1}}} \right\}$$Set of terminal symbols

$${\bf{S}}$$ Start symbol

Set of productions $${\bf{P}}$$

$${\bf{S}} \to {\bf{EF}}$$

$$\begin{array}{l}{\bf{F}} \to {\bf{0FA}}\\{\bf{F}} \to {\bf{1FB}}\\{\bf{F}} \to {\bf{\lambda }}\\{\bf{0A}} \to {\bf{A0}}\\{\bf{0B}} \to {\bf{B0}}\\{\bf{1A}} \to {\bf{A1}}\\{\bf{1B}} \to {\bf{B1}}\\{\bf{EA}} \to {\bf{E0}}\end{array}$$

$$\begin{array}{l}{\bf{EB}} \to {\bf{E1}}\\{\bf{E}} \to {\bf{\lambda }}\end{array}$$