GATE CSE 2016 Set 1 | Question: 43

Question

Consider the transition diagram of a PDA given below with input alphabet $\Sigma=\{a,b\}$ and stack alphabet $\Gamma = \{X,Z\}$. $Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA

Which one of the following is TRUE? 

• A. $L =\{a^nb^n\mid n \geq0 \}$ and is not accepted by any finite automata 
• B. $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is not accepted by any deterministic PDA 
• C. $L$ is not accepted by any Turing machine that halts on every input 
• D. $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is deterministic context-free

Comments

FIRST OF ALL WANT TO SAY....THAT ...IN PDA TWO CONDITION OF ACCEPTING LANGAUGE

1)  EMPTY STACK CONDION(IN THIS CASE FINALLY AFTER TRANSITION OF NULL ....STACK SHOULD BE EMPTY ...MEANS WHEN EVER STACK WILL BE EMPTY....AFTER TRANSITION OF STRING THEN..STRING WILL IN LANGUAGE)..

2)FINAL STATE CONDION (IN THIS CASE AFTER TRANSITION OF NULL.....STACK SHOULD CONTAIN STACK TOP SYMBOL......MEANS AFTER TRANSITION OF COMPLETE STRING ....WHEN EVER FINALLY GOT STACK INITIAL TOP SYMBOL ON STACK TOP THEN IT WILL BE ACCEPTABLE )

YOUR ANSWER :SUPPOSE I TAKE INPUT a ...then what will be the situation....let state (q0(initial),q1(middle),q2(last))
 

transition(q0,a,Z)/(q0,aZ)........it means at inial state ....get input a...stack symbol Z......then it push a on stack ..then now stack top a

now final situation will be ....

transition(q0,null,a)  :  there is no any transition for this......

now analyse the situation......

is stack is empty ..... answer is no(so in this condition string a is not acceptable)

now look second condition......is initial state is final state(yes)....butttttttttttttttttttttttttt..............(in this case stack top should contain initial top symbol Z)....but here stack top containning symbol a)...

so this is not final state pda condition....

SO PLLEASE SIR ...REVIEW THE ANSWER ONCE AGAIN...AFTER LOOKING ...ACCEPTING STATE CONDITION..IN PDA ...FROM ULLMANN)

IF I AM WRONG.....THEN PLEASE GIVE SOME SATISFACTORY ANSWER)

NOW...ACCORDING  TO QUESTION....IF I TAKE a^n  LANGUAGE..THEN.....AFTER TRANSITION OF ALL a's FOLLOWED BY NULL....FINAL SITUATION WILL BE (INITIAL STATE,NULL,X)...THIS IS NOT VALID FOR ACCEPTING STATE ...

SO ONLY ...A IS RIGHT ANSWER

---

no final answer is corrected

---

for a^n there is no epsilon transition defined here didn't  any one notice that in that case option D shouldn't be right ?

or can we neglect that?

why should we even for strings with a^n also end with epsilon right ?

---

@Arjun sir please clarify this doubt

---

but dcfl is not closed under union

---

same concept based

https://gateoverflow.in/2765/gate1996-13

 

---

@once_2019 when we say that a language is closed under some property, we guarantee that it will be closed in any case. But when we say that it is not closed, we say that it may not be closed. So the union of two DCFL is not closed means it may or may not be DFCL depending upon the language.

---

@once_2019 If you see first part of union then it is regular language &  union of DCFL with regular is DCFL.

Answer 1

Strings accepted at $I^{st}$ final state are $a^n\; ,\;n\geq0$ and strings accepted at $II^{nd}$ final state are $a^nb^n\;,\;n\geq 0$ (actually $n\geq 1$ at this state, $n=0$ already included at first state).

$L=\{a^n\;|\;n\geq 0\} \cup \{a^nb^n\;|\;n\geq0\}$
Language is deterministic context-free  accepted by DPDA (dpda is already given) and so by TM too, and not regular (as we need stack to implement it), and so cannot accepted by FA

Correct Answer: $D$

Comments

IN DPDA , IS UNION IS DECIDABLE OR NOT .?

---

@praveen saini This given pda is not DPDA, It is NDPA as it has epsilon(without reading any i/p symbol) transition, this makes multiple choices of states and violates the rule determinism.??

If wrong please correct me.

---

@Twinkle Shuklamay or may not be decidable

Answer 2

Ya it should be D option. As 1st state is also the final state

Comments

it accpepts aⁿbⁿ also.. and is deterministic too as can be seen from the diagram

Answer 3

As we know Acceptence of given string by PDA in two ways Either by

1. Acceptance by final state: ( If you are scanning the input, and at the end of string machine enters to one of the final state then string is accepted.)

2. Acceptance by Empty Stack: In this case we don't bother, machine enter into final state or not, if at end of string stack is empty then we can say string is accepted.

Option D is correct:  

Bcz in option D, if u take L= a^n, a is pushed into the stack  and it remains in first state only, which is marked as Final state so this string is accepted by PDA (Acceptence by final state)

  L= a^n b^n, as we know this string is accepted by given PDA as shown in given figure, this is also acceptence by final state). This language is not accepted by FA.

Regarding deterministic, in both the case we are deterministic to push a in to stack. So this is accepted by DPDA. so option D

Answer 4

the first state is accepting all strings of type aⁿ for n>0

and if a b comes it will make a transition to second state and it will reach empty stack only when all the a's are popped out of stack so it is accepting a^n.bⁿ   and  the given pda is dpda.

option d