StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q1SE

Expert-verifiedFound in: Page 901

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}\)

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.

(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}}\)

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}\)

(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}}\)).

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}\)

(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}\)

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\}\)

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}\)

94% of StudySmarter users get better grades.

Sign up for free