0

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

evinda
  • 7,823

1 Answers1

2

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

Denis
  • 6,945
  • 1
  • 21
  • 22
  • could you explain me why you put two $S$ at the first rule and two $T$ at the second? – evinda Jan 26 '14 at 19:54
  • 1
    if there is only one S, you cannot produce (a)(a). And if there is only one T, you cannot produce ((a)(a)). This allows to duplicate both the root expression and the inside expressions. – Denis Jan 26 '14 at 21:18
  • I understand..and something else is this rule $S \to \varnothing$ allowed or not? – evinda Jan 26 '14 at 21:39
  • And..with these rules,can we just have two pairs of parenthesis like that (()) or can it also be ((()))? – evinda Jan 26 '14 at 21:47
  • 1
    Yes you can add a rule $S\to \epsilon$ if you want the empty word in your language. You can derive $S\to (T)\to ((T))\to (((T)))\to(((A)))\to((()))$, because $T$ can unfold as many times as you want. – Denis Jan 26 '14 at 22:51
  • I understand...thank you very much!!! – evinda Jan 26 '14 at 22:56