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

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

It is violating prefix property then how can it accepted by any DPDA????Answer should be B.

---

prefix property is only for DPDA which accept string by Empty stack..
here final state method is used, so empty stack rule doesnot apply here

Check here: http://elearning.vtu.ac.in/e-con/FAFL/ch4/html/0040.htm

---

after all 'a' s pushed into the stack there is no ∈ transition on initial state i.e) ∈,z/z then how it accept the language {a^n/n>=0}

---

The initial state itself is the final state, isnt it?

---

@praveen saini Sir Yes D is correct I agree but why option A is not correct??

---

bcoz $L$ given in option D is correct, and that is wrong in option A

---

@praveen saini sir,

Option (A)as

$L=\{a^nb^n|n≥0\}$ and is not accepted by any finite automata 

As per option D is true for dcfl and in option (A) it talk about dfa&nfa then $a^nb^n$ should not be accepted by nfa&dfa should be right.

Please explain sir I am confused??

---

First of all, L is not equal to $\{a^nb^n:n\geq0\}$ so option A is wrong. No need to look anything else.

---

@Praveen Saini First of all, L is not equal to {aⁿbⁿ:n≥0} so option A is wrong. No need to look anything else.

Sir,L is not equal to WHAT? 

---

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 ?

@Praveen Saini sir

---

@Praveen sir, had been the first state not being a final state and only the last state a final state then, in that case, L would have been equal to as described in option A)

Am I right?

---

I think this DPDA has both acceptance by "empty stack" and "final state" as L= {aⁿ |n>=0} is accepted by a final state as no (∈, Z->Z) in the first state
and
L= {aⁿbⁿ | n>=0} is accepted by only when stack is emptied as we reach final state only when stack is empty((∈, Z->Z) present).
 

Then which one to consider? if consider it is as "empty stack" then the violation of prefix property makes it PDA.

@Bikram sir

@Arjun sir

---

how can we have both the kind of acceptances in the same PDA ? do u have any reference ? @bhuv

---

actually it was my dbout that i have commented above. But it got resolved today.

read this post to know more.

http://forum.thegatebook.in/t/gate2016-1-43-dpda-or-not/1024

---

in final state acceptance there will be atleast one final state and in empty stack acceptance there will be no final state but ultimately the stack should be empty upon reading the entire input :) thanks for the screen shots

---

can u please expalin this?

---

Also, the point to note is that the Language $\{a^n|n \geq 0\}$ is Accepted by PDA acceptance by Final state

And the Language $\{a^nb^n|n \geq 0\}$ is accepted by PDA acceptance by empty stack.

---

So if transition diagram is not given and only equation is given , then option B will be answer, since common prefix comes in picture?

---

Why is the given diagram considered as DPDA since there is not config defined for first state when input b and top of the stack is Z?

---

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