the grammar:
I tried to breakdown the problem but i am not sure what the end result expression could be.
I have to give an expression and try to describe this grammar.
Here's what i did for now :
I see that there's two possible starting words ( S non-terminal means start)
For $S \Rightarrow WTba$ i get :
$W^*\$(ba)^*ba$
W can be Wb or ab so we know the word will start by ab for sure : $ab(b^*(ab)^*)^*\$(ba)^*ba$
For $S \Rightarrow abUV$ i get :
$ab(ab)^*\$V$
since V can be Va or ba the word will end by ba for sure : $ab(ab)^*\$(a^*(ba)^*)^*ba $
From these two end result i can see that they are ALMOST the reversed language of each other but one has the letter b instead of a in the big loop $(a^*(ba)^*)^*$ vs $(b^*(ab)^*)^*$
But i can't manage to figure out a general expression and correctly describe this grammar, so if anyone could help out it would be greatly appreciated. Thanks.
Best Answer
You have the right idea, but you’ve lost the relationship between the part to the left of the $\$$ and the part to the right of it: you cannot express it in terms of Kleene stars. For instance, when you apply the production $T\to WTba$ $n$ times, you get the same number of $W$s as you do $ba$s, so you don’t get $W^*T(ba)^*$.
First, it’s clear that the language produced by $W$ is $abb^*$: the only possible derivations starting with $W$ have the form
$$W\Rightarrow^nWb^n\Rightarrow abb^n$$
for $n\ge 0$. Now let’s look at a derivation that starts by using the production $S\to WTba$. Since we know what $W$ does, we should concentrate on $T$: we can apply the production $T\to WTba$ $n$ times for any $n\ge 0$, but eventually we must apply $T\to\$$ in order to get rid of the $T$. Thus, we get derivations of the form
$$S\Rightarrow WTba\Rightarrow^n WW^nT(ba)^nba\Rightarrow WW^n\$(ba)^nba$$
for each $n\ge 0$. This will evidently generate the language described by the expression
$$(abb^*)^n\$(ba)^n\,,\tag{1}$$
where $n$ can be any positive integer.
The other half of the language can be analyzed similarly. $V$ generates everything of the form $baa^*$, so we end up with everything of the form
$$(ab)^n\$(baa^*)^n\tag{2}$$
for $n\ge 1$. Let $L_1$ be the language described by $(1)$ and $L_2$ the language described by $(2)$, so that we want the language $L=L_1\cup L_2$. $L$ can be described in just this way, but the description can perhaps be made a little nicer if we notice that $L_2$ can be obtained from $L_1$ (and vice versa) in a fairly simple way. Let
$$f:\{a,b\}\to\{a,b\}:x\mapsto\begin{cases} a,&\text{if }x=b\\ b,&\text{if }x=a\,, \end{cases}$$
and let $\hat f$ be the natural extension of $f$ to $\{a,b\}^*$. (E.g., $\hat f:(abbbab)=baaaba$.) Then
$$L_2=\{\hat f(v)\$\hat f(u):u\$v\in L_1\}\,,$$
and
$$L_1=\{\hat f(v)\$\hat f(u):u\$v\in L_2\}\,.$$
Thus, $L$ can be described simply in terms of $(1)$ and $\hat f$.