[Solved]: How to construct a grammar that generates language L?

Problem Detail: 

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

Asked By : Terry Light

Answered By : Terence Hang

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45724

3.2K people like this

 Download Related Notes/Documents