- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

A push down automata (PDA) can be formally described as seven tuples

**(Q, Σ,S, δ,q0,I,F)**

Where,

- Q is finite number of states
- Σ is input alphabet
- S is stack symbol
- Δ is the transition function: QX(Σ∪{e})XSXQ
- q0 is the initial state (q0 belongs to Q)
- I is the initial state top symbol
- F is a set of accepting states(F belongs to Q)

Construct PDA for 0^{n}1^{m}2^{m}3^{n} where n,m≥1.

So, the strings which are generated by the given language are −

L={0123,011223,001233….}

The number of 1’s and 3’s are same and number of 2’s and 1’s are same

**Construction of PDA for given problem**

The PDA is as follows −

**Step 1** − First 0’s are pushed onto the stack.

**Step 2** − Next 1’s are pushed into the stack.

**Step 3** − For every 2 as input a 1 is popped out of stack.

**Step 4** − If some 2’s are still left and top of stack is a 0 then string is not accepted by the PDA.

**Step 5** − If 2’s are finished and top of stack is a 0 then for every 3 as input equal number of 0’s are popped out of stack.

**Step 6** − If the string is finished and the stack is empty then the string is accepted by the PDA. Otherwise, the string is not accepted.

- Related Questions & Answers
- Construct PDA for L = {0n1m2(n+m) | m,n >=1}
- Construct PDA for accepting L = {anb(2n) | n>=1} U {anbn | n>=1}
- Construct Deterministic PDA for a^n b^n where n>=1
- Construct a Turing Machine for L = {a^n b^n | n>=1}
- Design NPDA for accepting the language L = {am b(2m) | m>=1}
- Construct a Turing Machine for language L = {0n1n2n | n≥1}
- Construct a Turing machine for L = {aibjck | i>j>k; k ≥ 1}
- Construct Turing machine for L = {an bm a(n+m) - n,m≥1} in C++
- Construct DPDA for a(n+m)bmcn n,m≥1 in TOC
- Construct DPDA for anbmc(n+m) n,m≥1 in TOC
- Construct ∈-NFA of Regular Language L = 0(0+1)*1
- Construct a Turing Machine for language L = {wwr | w ∈ {0, 1}}
- Construct DPDA for anbncm where, n,m≥1 in TOC
- Construct ∈-NFA of Regular Language L = (00)*1(11)*
- Construct Pushdown automata for L = {0n1m2(n+m) | m,n = 0} in C++

Advertisements