- Design context-free grammars for the following languages.
(a) The set of all strings of $a$’s and $b$’s that are not of the form $ww$, that is, not equal to any string repeated.
$S \rightarrow AB \mid BA \mid A \mid B$
$A \rightarrow a \mid aAa \mid aAb \mid bAa \mid bAb$
$B \rightarrow b \mid aBa \mid aBb \mid bBa \mid bBb$
(b) The set of all strings with twice as many $0$’s as $1$’s.
$S \rightarrow \epsilon \mid SS \mid 00S1 \mid 0S1S0 \mid 1S00$
- The following grammar generates the language of regular expression $0^* 1(0+1)^*$ :
$S \rightarrow A1B$
$A \rightarrow 0A\mid \epsilon$
$B \rightarrow 0B\mid 1B\mid \epsilon$
Give leftmost and rightmost derivations of the following strings:
(a) $00101$.
$S \Rightarrow_{\sf lm} A1B \Rightarrow_{\sf lm} 0A1B \Rightarrow_{\sf lm} 00A1B \Rightarrow_{\sf lm} 001B \Rightarrow_{\sf lm} 0010B \Rightarrow_{\sf lm} 00101B \Rightarrow_{\sf lm} 00101$
$S\Rightarrow_{\sf rm} A1B \Rightarrow_{\sf rm} A10B \Rightarrow_{\sf rm} A101B \Rightarrow_{\sf rm} A101 \Rightarrow_{\sf rm} 0A101 \Rightarrow_{\sf rm} 00A101 \Rightarrow_{\sf rm} 00101$
(b) $1001$.
$S \Rightarrow_{\sf lm} A1B \Rightarrow_{\sf lm} 1B \Rightarrow_{\sf lm} 10B \Rightarrow_{\sf lm} 100B \Rightarrow_{\sf lm} 1001B \Rightarrow_{\sf lm} 1001$
$S\Rightarrow_{\sf rm} A1B \Rightarrow_{\sf rm} A10B \Rightarrow_{\sf rm} A100B \Rightarrow_{\sf rm} A1001B \Rightarrow_{\sf rm} A1001 \Rightarrow_{\sf rm} 1001 $
(c) $00011$.
$S \Rightarrow_{\sf lm} A1B \Rightarrow_{\sf lm} 0A1B \Rightarrow_{\sf lm} 00A1B \Rightarrow_{\sf lm} 000A1B \Rightarrow_{\sf lm} 0001B \Rightarrow_{\sf lm} 00011B \Rightarrow_{\sf lm} 00011$
$S\Rightarrow_{\sf rm} A1B \Rightarrow_{\sf rm} A11B \Rightarrow_{\sf rm} A11 \Rightarrow_{\sf rm} 0A11 \Rightarrow_{\sf rm} 00A11 \Rightarrow_{\sf rm} 000A11 \Rightarrow_{\sf rm} 00011$
- For the grammar and each of the strings in Exercise 2, give parse trees.
- Consider the set of all strings of balabced parentheses of two types, round and square. An Example of where these strings come from is as follows : $f(a[i]*(b[i][j],c[g(x)]),d[i])$. It becomes the balanced -parenthesis string $([\ ]([\ ][\ ][()])[\ ])$.
Design a grammar for all and only the strings of round and square parenthsis that are balanced.
$B \Rightarrow BB\mid (B)\mid [B]\mid \epsilon$
- Consider the grammar
$S \rightarrow aS\mid aSbS\mid \epsilon$.
This grammar is ambiguous. Show in particular that the string $aab$ has two :
(a) Parse trees.
1.
2.
(b) Leftmost derivations.
- $S \Rightarrow_{\sf lm} aSbS \Rightarrow_{\sf lm} aaSbS \Rightarrow_{\sf lm} aabS \Rightarrow_{\sf lm} aab$
- $S \Rightarrow_{\sf lm} aS \Rightarrow_{\sf lm} aaSbS \Rightarrow_{\sf lm} aabS \Rightarrow_{\sf lm} aab $
(c) Rightmost derivations.
- $S\Rightarrow_{\sf rm} aSbS \Rightarrow_{\sf rm} aSb \Rightarrow_{\sf rm} aaSb \Rightarrow_{\sf rm} abb$
- $S\Rightarrow_{\sf rm} aS \Rightarrow_{\sf rm} aaSbS \Rightarrow_{\sf rm} aaSb \Rightarrow_{\sf rm} aab$