retagged by
2,115 views

1 Answer

Best answer
5 votes
5 votes

$L = a \left(a + b\right)^+ b$

In $q_0$ when stack is empty and an $a$ comes, $a$ is pushed on stack. After this for either $a$ or $b$, we reach $q_1$ without modifying the stack. In $q_1$ we can ignore all a's and b's without modifying the stack. Finally, we can move to $q_2$ on a $b$ and this pops the $a$ on stack (there is non-determinism here for the given PDA). And now stack is empty and PDA reached final state. So, $L$ is regular but infinite. 

edited by

Related questions

2 votes
2 votes
1 answer
2
Anjana Babu asked Nov 24, 2016
1,667 views
Please Explain why the following is accpeted/rejected by PDA . ( Need detail explanation )S1 = { 0n 0m 1n 0m | n,m>0 }S2 = { 0n 0m 1n 1m 0m | n,m>0 }S3 = { am 0m 1n...