find the grammar for the language that contains all and only the words that have the form: $(a ... b c (b) (c c) b ) (a (c b) c ... a (b) a b)$

63 Views Asked by At

Give a context-free grammar for the language,with $\Sigma=\{(,),a,b,c\}$,that contains all and only the words that have the following form: $(a ... b c (b) (c c) b ) (a (c b) c ... a (b) a b)$ ,that is a text with balanced parenthesis,that contains any subwords of the symbols $a,b,c$ between any pair of matching parenthesis and only there-(for example the word $(a)b(c)$ is not allowed,because of the appearance of $b$).

1

There are 1 best solutions below

6
On BEST ANSWER

Here is a grammar for your language:

$\begin{array}{l} S\to SS|(T)\\ T\to (T)|TT|A\\ A\to aA|bA|cA|\epsilon. \end{array} $