Question

Please Help with this questions with short explanation thank you :)

Consider the pushdown automaton with the following transition rules: 1.8(0,0,20) = {(q,XZ0)} 2. 8(9,0,X) = {(q,XX)} 3. 8(q,1,X) = {(q,x)} 4. 8(q,£,X) = {(p,ɛ)} 5. 8(p,£,X) = {(p,ɛ)} 6.8(p,1,X) = {(p,XX)} 7. 8(p,1,20) = {(p,ɛ)} From the ID (p,1101,XXZ0), which of the following ID's can NOT be reached? (p,101,XZO) (p,101,XXXZO) (2,01,XXXXXZO) O (p,01,8)

Answer 1

CONCEPT FOR PDA-

PDA STANDS FOR PUSH DOWN AUTOMATA. THIS AUTOMATA IS USED TO GENERATE CONTEXT FREE GRAMMER. IN THIS WE HAVE A STACK AND A PUSH AND A POP OPERATION.

A PDA IS DEFINED USING THE FOLLOWING PARAMETERS-

Q is any general state.
? is the set of input symbols
q0 is the initial state
Z it denotes the stack symbol which is usually present in stack
F is the set of final states
d is a transition function which maps Q x {S ? ?} x G into Q x G*. In a given state, PDA will read input symbol and move to a new state and change the symbol of stack.

Question 1 -

answer - option c

Explanation -

Try to understand that we can carry as many as epsilon transitions as we want .

so , whenever we carry epsilon transition with X at top it will pop that X.

so , option A is correct as by following transitions

1. epsilon and pop X

2. from 1 insert a X

3. epsilon and pop X

Similarly option B is also correct

by just a single transition

from 1 insert a X

option c is incorrect because only this option have more number of X as compared to more number of 1 which is not possible as one 1 can produce only 1 X

option d is correct by many epsilon transitions

Question 2

Answer-

option d is correct because

Explanation -

initially the string will b in q0 state

To go to q3 you first have to reach the q2 state

that can only be reached if the string starts with a "b"

so option d is correct

THANK YOU FOR USING CHEGG. KEEP CHEGGING.

ASK ANY DOUBTS IN COMMENTS