Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
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.
