I need to convert the following language to a CFG $$ L = \{\ a^n b^{n+k} a^k \in \{a,b\}^* \ |\ n \ge 0\ ,\ k\ge 0 \} \ . $$ So far I have: $$ \begin{aligned} S &\Rightarrow SASBSA \ ,\\ A &\Rightarrow a\ ,\\ B &\Rightarrow bb|b\ . \end{aligned} $$ But I don't think this is correct. It's not quite a palindrome as $n$ and $k$ can be odd. I'm struggling with the $n+k$ part.
Asked
Active
Viewed 147 times
0
-
1Please show your attempt and add context. – Jan 04 '23 at 14:21
-
Hint: It might help to view the general element as $a^n b^n \cdot b^k a^k$ and then split the generation of this element into the two parts. – Daniel Schepler Jan 04 '23 at 14:56
-
ah ok so the same amount of a's and b's, then the same amount of b's and a's, excuse the formatting but like: S->TQ, T->SASBS, Q->SBSAS, A->a, B->b – moonraker Jan 04 '23 at 15:40
-
How do you get rid of the occurrence of either $S$, or $T$ (using the above rules)? Why not $S\to TU$, and $T$ can generate only $aTb$ or $T'$, and $U$ only $bUa$ or $U'$, and arrange that $T',U'$ are then replaced only by the empty string. – dan_fulea Jan 04 '23 at 16:52
-
not sure i understand that, my knowledge is very limited. What does $T'$ and $U'$ mean? – moonraker Jan 04 '23 at 16:59
-
I think what @dan_fulea is suggesting is something like $T\Rightarrow aTb | T'$, $T'\Rightarrow \varepsilon$, and similarly for $U$ and $U'$. (Though it's pretty much equivalent to use just $T \Rightarrow aTb | \varepsilon$.) – Daniel Schepler Jan 04 '23 at 17:57
-
thanks, so S ⇒ TU, T ⇒ aTb | T', U ⇒ bUa | U', T'⇒ , U'⇒ ? – moonraker Jan 05 '23 at 09:10
-
I'm not familiar with the ′ syntax (the apostrophe bit), could ′ be replaced by another variable name, X, for example? – moonraker Jan 05 '23 at 09:12
1 Answers
0
Since we can have $a^nb^n$ and $b^na^n$ we can generate our strings by multiplying a prefix $P$ by a suffix $Q$. Let $S$ be our start symbol. $$S\to\epsilon$$ $$S\to P$$ $$S\to Q$$ $$S\to PQ$$ $$P\to aPb$$ $$Q\to bQa$$ $$P\to ab$$ $$Q\to ba$$
John Douma
- 11,426
- 2
- 23
- 24