I was asked to define the language which is produced by the following grammar:

$G = (V, \Sigma, S, P)$

$V = \{S, A, B\}$

$\Sigma = \{a, b, c\}$

\begin{equation} P= \begin{cases} S \rightarrow cA | bB\\ A \rightarrow c \\ B \rightarrow aB|b \end{cases} \end{equation}

Obviously, you can produce $c^n$ and $b^n$, but since we can also produce $ccbab$ for example, I do not know how to find a formular for the language $L(G)$

Any help would be really appreciated!

  • $\begingroup$ How can you produce ccbab? $\endgroup$ – Yuval Filmus Jan 14 '18 at 17:03
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jan 14 '18 at 20:35

Let's start with the nonterminal $B$. Since all productions of the form $B \to \alpha$ involve only $B$ (and no other nonterminal), we can easily find $L(B) = a^*b$ using Arden's rule. We also have $L(A) = c$. Finally, $$ L(S) = L(cA) \cup L(bB) = cc + ba^*b. $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.