1
$\begingroup$

I try to find a context free grammar for the language $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$. There is a hint in the task that one should first construct the context free grammar for cases such as $L_1 = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a > \vert v \vert_a\}$ and later combine all of these.

I would appreciate a hint to come up with $L_1$. I do not know how construct $u\#v$ such that $u$ and $v$ are free independent from each other except of the fact that $u$ has more $a$'s than $v$. I tried to build my language around the $\#$ and also tried to move the $\#$ in the direction of the most appearing $a$'s but none of my attempts worked.

What is the proper way to tackle such constructions in general?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ @greybeard Thank you. I don't think it is nessecary to keep this discussion here, so I deleted the other comments. $\endgroup$ – Discrete lizard♦ May 18 '20 at 10:46
3
$\begingroup$

I'll just show how to build a grammar for $L_1 = \{ u\#v, |u|_a > |v|_a \}$. Then it'll be straightforward to combine 4 similar grammars into a grammar for $L$.

The idea is to write $u\#v$ as $xay\#v$ with $x,y,v \in \{a,b\}^*$ and $|y|_a = |v|_a$. The construction of $y\#v$ is handled by the non-terminal $Z$ which "grows" it from the center.

$$ \begin{align*} S &\to aS \mid bS \mid aZ \\ Z &\to bZ \mid Zb \mid aZa | \,\# \end{align*} $$

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks for your help. I will be able to solve the other grammars with your solution of this example. I am new to this topic and have a hard time to think into this construction tasks. $\endgroup$ – Ludwig M May 16 '20 at 17:39
  • 1
    $\begingroup$ You're welcome. Often times a language can be thought as the union or concatenation or simpler languages. $\endgroup$ – Steven May 16 '20 at 17:40
  • 1
    $\begingroup$ Why? The part preceding $aZ$ can have any number of $a$s and $b$s. $\endgroup$ – Steven May 17 '20 at 8:13
  • $\begingroup$ @greybeard Consider $S \Rightarrow bS \Rightarrow baS \Rightarrow baaS \Rightarrow baaaZ \Rightarrow baaaZb \Rightarrow baaa\#b$. Obviously $baaa$ does have $3$ $a$'s more than $b$. $\endgroup$ – Ludwig M May 17 '20 at 20:48
  • 1
    $\begingroup$ Correct - I missed that you have productions with the start symbol on the right side. $\endgroup$ – greybeard May 17 '20 at 20:50

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.