The Gateway to Computer Science Excellence
+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 by Junior (941 points) | 249 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.
by Junior (807 points)
Thank you

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
104,979 users