MHB Show that language is accepted by a pushdown automaton

[evinda]

The textbook by Lewis and Papadimitriou also does not have anything on deterministic context-free grammars, though it has a section on deterministic PDAs. Even Wikipedia, which has a detailed article on regular context-free grammars, does not give the definition of deterministic CFGs, though it has a small article about them. So, do you plan to undertake a little research project to study deterministic CFGs as a part of solving one problem?

I try to describe the function of the PDA:
For each $a$ that is read,we put an $a$ in the stack.
When,the first $b$ is read,we begin to pop an $a$ for each $b$.
But..how can the stack get empty,if we know that the number of $a$ that is read shouldn't be equal to the number of $b$ ??

 

[evinda]

I try to describe the function of the PDA:
For each $a$ that is read,we put an $a$ in the stack.
When,the first $b$ is read,we begin to pop an $a$ for each $b$.
But..how can the stack get empty,if we know that the number of $a$ that is read shouldn't be equal to the number of $b$ ??

Is it maybe like that:when the stack gets empty,we will have an accepting state and then it will be allowed that the automaton reads more $b$s??But,if it is like that,isn't it possible that the number of $a$ is equal to the number of $b$ ??

 

[I like Serena]

I try to describe the function of the PDA:
For each $a$ that is read,we put an $a$ in the stack.
When,the first $b$ is read,we begin to pop an $a$ for each $b$.
But..how can the stack get empty,if we know that the number of $a$ that is read shouldn't be equal to the number of $b$ ??

Is it maybe like that:when the stack gets empty,we will have an accepting state and then it will be allowed that the automaton reads more $b$s??But,if it is like that,isn't it possible that the number of $a$ is equal to the number of $b$ ??

Indeed.
So if the stack gets empty (except for the initial stack symbol), we should make sure we're not in an accepting state.
Either we have to accept the string before that happens, or we have to make sure we read more $b$'s after it happens.

 

[evinda]

Indeed.
So if the stack gets empty (except for the initial stack symbol), we should make sure we're not in an accepting state.
Either we have to accept the string before that happens, or we have to make sure we read more $b$'s after it happens.

Nice...Thank you very much for your help! :D