- 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

Generate the push down automata (PDA) that recognizes the language E={aibj| i is not equal to j and I is not equal to 2j}.

Consider the two languages as given below −

L1={aibj|i,j>=0 and i>2j}L2={aibj|i,j>=0 and i<2j}

Convince yourself that L=L1UL2

In L1, the number of a's are more than double of b's so L1 as follows −

S1->aA

A->aaAb|aA|epsilon

In L2, the number of a's are less than double the number of b's

So the CFG for L2 becomes as follows −

S2->Bb|aBb

B->Bb|aBb|aaBb|epsilon

S->S1|S2

L1: {aibj:i>2j}

L2:{aibj: i<2j}

- Related Questions & Answers
- Design a TM which recognizes palindromes over = {a, b}
- Construct a PDA that accepts (a,b)* language but not contain bbbb?
- Construct a PDA for language L = {0n 1m2m3n | n>=1, m>=1}
- Explain the balancing parenthesis of PDA
- What is the Instantaneous description of PDA?
- Design NPDA for accepting the language L = {am b(2m) | m>=1}
- Design a DFA accepting a language L having number of zeros in multiples of 3
- Which is the best Programming language for career growth and development?
- Explain top-down design and structure chart of function in C language
- Explain Turing Machine variant Two Stack PDA?
- Design a Keylogger in Python
- Design A Leaderboard in C++
- Explain the design and implementation of a simple microsequencer?
- The benefits of good Database Design
- How to design a modern Website?

Advertisements