I'm in a Formal languages class and have a grammar quiz coming up. I'm assuming something like this will appear.

Consider the alphabet $\Sigma$ = {a, b, c}. Construct a grammar that generates the language $L = \{bab^nabc^na^p \mid n ≥ 0, p ≥ 1\}$. Assume that the start variable is $S$.

  • $\begingroup$ and the problem is...? if there is no restriction on the grammar, there are many possible solution; I assume you meant a context-free grammar. $\endgroup$ – Ran G. Aug 31 '15 at 4:50
  • $\begingroup$ What research have you done? What have you tried? Have you tried using the techniques in cs.stackexchange.com/q/18524/755? This question looks like it is answered by the answers there. $\endgroup$ – D.W. Aug 31 '15 at 6:21

One possible grammar is: $G = (N, \Sigma, P, S)$, where

$N = \{S,U,V\}$

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

$P = \{ S \to baUV, U \to ab|bUc, V \to a|aV \}$

The key observation here is breaking $bab^nabc^na^p$ into 3 parts, $ba$, $b^nabc^n$, and $a^p$, one fixed, one growing bidirectionally, and one simple repeatition. Express the growing patterns first, then merge them along with the fixed parts.


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.