1
$\begingroup$

I'm trying to get CFGs for these two languages which still remain unsolved in my practice problems sheet:

$L = \{ a^kb^ra^m | m=k+r\}$

$L = \{ a^nb^m | 1\leq n\leq 2m\}$

With the first one, I thought of this:

$$S\rightarrow aSa | T$$ $$T\rightarrow b T a | \epsilon$$

but what if $k>r$ or $r>k$?

With the second one, I think it is really simple but I cannot wrap my mind with $1\leq n\leq 2m$ (maybe I'm special...), should I have at least as many $a's$ as the double of $b's$ but not strictly? how could I specify that?

$\endgroup$
1
$\begingroup$

You can write the first language as $$ \{ a^k b^r a^r a^k \mid k,r \geq 0 \}. $$ The corresponding context-free grammar is exactly the one you give. If you apply $k$ times the rule $S \to aSa$ and $r$ times the rule $T \to bTa$, then you will get $a^k b^r a^r a^k$.

As for the second language, let us start with the slightly easier $$ \{ a^n b^m \mid n \le 2m \}. $$ For each $b$ that you add, you can add up to two $a$'s. This leads to the grammar $$ S \to Sb \mid aSb \mid aaSb \mid \epsilon. $$ In your case, you have to guarantee at least one $a$. Write this as follows: $$ \{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m+1 \} = \{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m \} \cup \{ a^{n+2}b^{m+1} \mid 0 \leq n \leq 2m \}. $$ Thus you can add the following rules to the preceding grammar, making $T$ the new starting symbol: $$ T \to aSb \mid aaSb. $$

$\endgroup$
1
  • $\begingroup$ Thank you! I had missed that detail in the first grammar, and your explanation for the second one was very helpful. I have to keep reminding myself to divide into smaller problems... $\endgroup$
    – Lightsong
    Dec 14 '20 at 8:33

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.