CIDA Lab @ UoS

Formal Language and Automata Homework 6 Answer

       

  1. 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$

$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$

   

  1. 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$

   

  1. For the grammar and each of the strings in Exercise 2, give parse trees.

3a 3b 3c

   

  1. 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$

   

  1. 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. 5al 2. 5ar

(b) Leftmost derivations.

  1. $S \Rightarrow_{\sf lm} aSbS \Rightarrow_{\sf lm} aaSbS \Rightarrow_{\sf lm} aabS \Rightarrow_{\sf lm} aab$
  2. $S \Rightarrow_{\sf lm} aS \Rightarrow_{\sf lm} aaSbS \Rightarrow_{\sf lm} aabS \Rightarrow_{\sf lm} aab $

(c) Rightmost derivations.

  1. $S\Rightarrow_{\sf rm} aSbS \Rightarrow_{\sf rm} aSb \Rightarrow_{\sf rm} aaSb \Rightarrow_{\sf rm} abb$
  2. $S\Rightarrow_{\sf rm} aS \Rightarrow_{\sf rm} aaSbS \Rightarrow_{\sf rm} aaSb \Rightarrow_{\sf rm} aab$
Search