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.
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$– plshelpJul 8, 2022 at 16:34
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Jul 8, 2022 at 19:36
$\begingroup$
$\endgroup$
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
