Log In
1 vote
In certain Pushdown Automata, will the input string considered accepted if while reading it we reach to final state but

1) the stack in not empty and contain few symbols?


2) there is still some remaining part of the string to be read(on processing which we might end up on some non-final state again).

An elaborate answer will be highly appreciated.
in Theory of Computation 424 views

1 Answer

2 votes
Point number one the pushdown automata will accept the language by the property of acceptance by final state it does not matter what symbols are remaining in the stack but the input string should be completely scanned.

For point number 2 if a string does not belong to a language then it will not accepted by a pushdown automata or  as you told it might lead to a non final state on scanning the complete string so to accept any string first it should be completely scanned and then reach to final state or can be accepted by emptying the stack.

Pushdown automata will not accept a string on scanning half.
Thank you

Related questions

0 votes
0 answers
given a pushdown automata that receives L by getting to an accepting state, how can a pushdown automata be built, so that it accepts L*? (might use a “double bottom” if needed)?? i don’t know how to solve it and would appreciate any kind of help! studying for exam and must learn how to solve it
asked Jan 16, 2019 in Theory of Computation anonymous 80 views
0 votes
0 answers
Options: $\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \} \cup \left \{ b^{n} | n\geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}\right )^{m}a | n,m \geq 0 \right \}$ $NONE$
asked Dec 10, 2018 in Theory of Computation jatin khachane 1 270 views
2 votes
0 answers
The language {w| the length of w is odd and it's middle symbol is 0, Wε(0+1)*} Why do we need a PDA for above language. I don't think we need a PDA for this language. I wrote the following RE. Tell me whats wrong in it:- [(0+1)(0+1)(0+1)]+0[(0+1)(0+1)(0+1)]+ + (other small left over strings like 0,101,100,001,000..... which are not covered in first part of expression)
asked Nov 29, 2017 in Theory of Computation ♥_Less 184 views