-1
$\begingroup$

I got a question: Design a pushdown automata that can recognize strings in L= {$ a^n b^{2n} c^{3n} | n ≥ 0 $} . I tried to think and design it, but I couldn't find it. The best that I can think of is L= {$ a^n b^{m} c^{m+n} | m,n ≥ 0 $} . I only can make sure that c appears as much as a+b appear. So, I'm wondering, is this language context free? Could we make a PDA for it? Thank you.

$\endgroup$
1
  • $\begingroup$ Even $a^nb^nc^n, n \geq 0$ is not context-free (proof). You can create a proof that $a^nb^{2n}c^{3n}$ is not CF similarly. $\endgroup$
    – plshelp
    Commented Jul 8, 2022 at 16:34

2 Answers 2

0
$\begingroup$

For $L= \{a^n b^{2n} c^{3n} | n ≥ 0 \}$ you will be failed to make PDA with one-stack. Because here is two comparisons, one $a$ should be checked against with $2b$ and $3c,$ but when you complete one $a$ checked against with $2b$ then stack will be empty, and there will be pending of $c$'s computation. This two comparison intuitively proved that your language is CSL accepted by LBA.

$\endgroup$
0
$\begingroup$

Consider this homomorphism: $ f(a)=a\ ,f(b)=bb,\ f(c)=ccc $

Context free languages are close to revered homomorphism

What is $ f^{-1}(L)? $

I hope that gives you a hint

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.