The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

0 votes

**its a DCFL.** how?

lets break it..

let the required states be ** q0,q1=non final states** and

**case 1**:

we can goto final state without reading anything directly from qo to q4.

($,ε,ε) = means if stack empty we can goto final state.

at state q0 :

(a,ε,a) means a can be pushed into the state qo without reading anything from the input.

at state q4 : its a null statement as once stack is empty we will goto state q4 than how will we have a again..

(ε,a,ε) means pop a without reading anything from state q4.

* conclusion for case 1 : it accepts *ε

**case 2:**

(b,a,ε) : for every b pop each a and soon as we have loop for state q1 .

($,ε,ε) means if stack empty goto state q3(final state).

**conclusion : it can accept strings of a ^{n}b^{n } : where n>=1**

so we conclude that the given pda accepts ε , a^{n}b^{n } : where n>=0 (including ε also). =** (DCFL)**

so the required languauge is a** DCFL overall. **

the question has asked for **complement of L**. which is also a **dcfl.**

0

@shaikh yes i didnt noticed that ($,ε,ε) which says if stack empty goto state q4... and if stack was empty why we need to pop a again... at q4 isnt that a null statement.

0

@srestha mam :here it means δ(q1,b,a)={(q1,ϵ)} means pop each a on seeing a b. or for every b pop each a. there is one pop for q0 to q1 and than it will continue for q1.

0

but PDA needs initial stack symbol right?

https://stackoverflow.com/questions/29568428/why-push-down-automata-need-a-initial-stack-symbol

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,532 questions

54,126 answers

187,326 comments

71,046 users