1
$\begingroup$

so the book that I'm reading says this is a deterministic context free language $L = \{a^n b^n | n>0 \}$ $\cup$ $\{ a^n b^{2n} | n < 100 \}$

But i think this is wrong Because :

at the beginning of building the DPDA, we have to decide whether we should go with the first one or the second, and considering both of them start with a there is just no way we could build a DPDA right?? or am i wrong?

i also tried solving this by first building the $a^nb^n$ and then going for the second one if the stack is not empty, but still couldn't come up with anything, i tried putting 2 a's for every a input but didn't work

so how is the book saying this can be build with a DPDA?

Also i have to say I KNOW that non infinite languages are regular, but this one is not infinite!

Improve this question
$\endgroup$
1
$\begingroup$

Maybe you can create 100 states that push two $a$'s onto the stack for every $a$, and then pop these $a$'s for every $b$. In the event of getting to the 100th state, when you read the 101st $a$, pop 100 $b$s from the stack and continue as you would for the first language alone.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Yes i tried doing that but doesn't work, because for example if the input is $a^{20}b^{20}$ then after reading all the a's and pushing 40 a's into stack and then popping 20 a's by reading all the b's the stack won't be empty and then we won't accept this string $\endgroup$ – John P Jan 20 '18 at 17:53
  • $\begingroup$ So you wanna write a DPDA that accepts by empty stack, not by final state? If you just wanna show that this language is deterministic, it's enough to build a DPDA that accepts by final states. $\endgroup$ – matheussilvapb Jan 20 '18 at 17:58
  • $\begingroup$ No it doesn't matter that its accepting by final state or not, it just needs to be deterministic, but using the method of pushing 2 a's for every one a input doesn't work in either way. $\endgroup$ – John P Jan 20 '18 at 18:09
  • $\begingroup$ Could you give an example string that doesn't work? $\endgroup$ – matheussilvapb Jan 20 '18 at 18:11
  • $\begingroup$ Maybe i'm not getting how you build the machine, can you please explain how it would work for $a^2b^2$ ? $\endgroup$ – John P Jan 20 '18 at 18:15

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.