Question 1

$\text { The productions of a phrase-structure grammar are } S \rightarrow S 1 , S \rightarrow 0 A , A \rightarrow 1 \text {. Find a derivation of } 0111$ .

Accepted Answer

Apply the production $S \rightarrow S 1$ twice to obtain $S 11$. Then apply $S \rightarrow 0 A$ to obtain $0 A 11$. Then apply $A \rightarrow 1$ to obtain 0111 .

Question 2

Suppose A = {0, 1}. Describe all strings belonging to A∗.

Accepted Answer

A∗ consists of all strings of 0's and 1's, including the empty string.

Question 3

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of

Accepted Answer

$$S \Rightarrow 1 S 0 \Rightarrow 11 S 00 \Rightarrow 110 A 00 \Rightarrow 110000$$

Question 4

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 0011.

Accepted Answer

The answer of Suppose a phrase-structure grammar has productions S...

Question 5

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 01.

Accepted Answer

The answer of Suppose a phrase-structure grammar has productions S...

Question 6

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 011111.

Accepted Answer

The answer of Suppose a phrase-structure grammar has productions S...

Question 7

Suppose  V={S, A, a, b}, T={a, b} , and  S  is the start symbol. Find a set of productions that includes $S \rightarrow A a$ and $A \rightarrow a$ and generates the language  {a, a a} .

Accepted Answer

The answer of Suppose  V={S, A, a, b}, T={a,...

Question 8

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 01.

Accepted Answer

The answer of Suppose a phrase-structure grammar has productions S...

Question 9

Let  G  be the phrase-structure grammar with vocabulary  V={A, B, 0,1, S} , terminal elements  T={0,1} , start symbol  S , productions  P=  $\{ S \rightarrow A B 0 , A B \rightarrow 1 , A \rightarrow 0 , B \rightarrow A B \}$ from  S ?   
(1) 000,  (2) 11, (3) 010, (4) } 0000,   (5)  0001, (6) 110, (7)  0010

Accepted Answer

The answer of Let  G  be the phrase-structure...

Question 10

Find a production of the form "A → ____" such that S → 1S , S → 0A, A → ____ produces {1ⁿ00 | n ≥ 0}.

Accepted Answer

The answer of Find a production of the form "A...

Question 11

Let  G  be the phrase-structure grammar with vocabulary  V={A, B, a, b, S} , terminal element set  T={a, b} , start symbol  S , and production set  P=  $\{ S \rightarrow A B a , S \rightarrow B a , A \rightarrow a B , A B \rightarrow b , B \rightarrow a b \}$
are derivable from S ? 
(1)  ba ,
(2)  ab ,
(3) baab,
(4) aababa,
(5)  aba

Accepted Answer

The answer of Let  G  be the phrase-structure...

Question 12

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of

Accepted Answer

The answer of Suppose a phrase-structure grammar has productions S...

Question 13

Find a set of two productions that produces $\left\{ 1 ^ { 2 n } \mid n > 0 \right\}$

Accepted Answer

The answer of Find a set of two productions that...

Question 14

Suppose  V={S, A, a, b}, T={a, b} , and  S  is the start symbol. Find a set of productions that includes $S \rightarrow A a$ and $A \rightarrow a$
 and generates the language  {a, b, b a, b a a} .

Accepted Answer

The answer of Suppose  V={S, A, a, b}, T={a,...

Question 15

Let  G  be the phrase-structure grammar with vocabulary  V={A, B, a, b, S} , terminal element set  T={a, b} , start symbol  S , and production set  P=  $\{ S \rightarrow A B a , S \rightarrow B a , A \rightarrow a B , A B \rightarrow b , B \rightarrow a b \}$
are derivable from  A  ?
(1) babaa,
(2)  aab ,
(3)  bba

Accepted Answer

The answer of Let  G  be the phrase-structure...

Question 16

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of 00.

Accepted Answer

The answer of Suppose a phrase-structure grammar has productions S...

Question 17

Let  G  be the phrase-structure grammar with vocabulary  V={A, B, a, b, S} , terminal element set  T={a, b} , start symbol  S , and production set  P=  $\{ S \rightarrow A B a , S \rightarrow B a , A \rightarrow a B , A B \rightarrow b , B \rightarrow a b \}$ - Which of these are derivable from ABa?
(1)  ba ,
(2)  abb ,
(3)  aba ,
(4)  b ,
(5)  aababa

Accepted Answer

The answer of Let  G  be the phrase-structure...

Question 18

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 0100.

Accepted Answer

The answer of Suppose a phrase-structure grammar has productions S...

Question 19

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 010.

Accepted Answer

The answer of Suppose a phrase-structure grammar has productions S...

Question 20

Find a production of the form "A → ____" such that S → 0A, A → ____ produces {00}.

Accepted Answer

The answer of Find a production of the form "A...

Quiz 13: A: Modeling Computation

$\text { The productions of a phrase-structure grammar are } S \rightarrow S 1 , S \rightarrow 0 A , A \rightarrow 1 \text {. Find a derivation of } 0111$ .

Suppose A = {0, 1}. Describe all strings belonging to A∗.

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 0011.

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 01.

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 011111.

Suppose V={S, A, a, b}, T={a, b} , and S is the start symbol. Find a set of productions that includes $S \rightarrow A a$ and $A \rightarrow a$ and generates the language {a, a a} .

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 01.

Let G be the phrase-structure grammar with vocabulary V={A, B, 0,1, S} , terminal elements T={0,1} , start symbol S , productions P= $\{ S \rightarrow A B 0 , A B \rightarrow 1 , A \rightarrow 0 , B \rightarrow A B \}$ from S ? (1) 000, (2) 11, (3) 010, (4) } 0000, (5) 0001, (6) 110, (7) 0010

Find a production of the form "A → " such that S → 1S , S → 0A, A → produces {1ⁿ00 | n ≥ 0}.

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of

Find a set of two productions that produces $\left\{ 1 ^ { 2 n } \mid n > 0 \right\}$

Suppose V={S, A, a, b}, T={a, b} , and S is the start symbol. Find a set of productions that includes $S \rightarrow A a$ and $A \rightarrow a$ and generates the language {a, b, b a, b a a} .

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of 00.

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 0100.

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 010.

Find a production of the form "A → " such that S → 0A, A → produces {00}.

Quiz 13: A: Modeling Computation

Suppose A = {0, 1}. Describe all strings belonging to A∗.

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 0011.

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 01.

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 011111.

Suppose V={S, A, a, b}, T={a, b} , and S is the start symbol. Find a set of productions that includes S→AaS \rightarrow A aS→Aa and A→aA \rightarrow aA→a and generates the language {a, a a} .

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 01.

Find a production of the form "A → ____" such that S → 1S , S → 0A, A → ____ produces {1n00 | n ≥ 0}.

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of

Find a set of two productions that produces {12n∣n>0}\left\{ 1 ^ { 2 n } \mid n > 0 \right\}{12n∣n>0}

Suppose V={S, A, a, b}, T={a, b} , and S is the start symbol. Find a set of productions that includes S→AaS \rightarrow A aS→Aa and A→aA \rightarrow aA→a and generates the language {a, b, b a, b a a} .

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of 00.

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 0100.

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 010.

Find a production of the form "A → ____" such that S → 0A, A → ____ produces {00}.

Suppose V={S, A, a, b}, T={a, b} , and S is the start symbol. Find a set of productions that includes $S \rightarrow A a$ and $A \rightarrow a$ and generates the language {a, a a} .

Find a production of the form "A → " such that S → 1S , S → 0A, A → produces {1ⁿ00 | n ≥ 0}.

Find a set of two productions that produces $\left\{ 1 ^ { 2 n } \mid n > 0 \right\}$

Suppose V={S, A, a, b}, T={a, b} , and S is the start symbol. Find a set of productions that includes $S \rightarrow A a$ and $A \rightarrow a$ and generates the language {a, b, b a, b a a} .

Find a production of the form "A → " such that S → 0A, A → produces {00}.