Scribd
Upload
1 views1 page

Assignment 4 Comp

The document is an assignment for the Theory of Computations course at Samarth College of Engineering for the academic year 2025-26. It includes various tasks such as designing Pushdown Automata (PDA) for specific languages, simulating PDAs with given input strings, comparing Finite Automata and PDA, and defining a Post machine. Additionally, it requires explanations of PDA applications and constructing PDAs from context-free grammars.

Uploaded by

Pragati Shirole
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1 views1 page

Assignment 4 Comp

The document is an assignment for the Theory of Computations course at Samarth College of Engineering for the academic year 2025-26. It includes various tasks such as designing Pushdown Automata (PDA) for specific languages, simulating PDAs with given input strings, comparing Finite Automata and PDA, and defining a Post machine. Additionally, it requires explanations of PDA applications and constructing PDAs from context-free grammars.

Uploaded by

Pragati Shirole
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

SAMARTH COLLEGE OF ENGINEERING BELHE

Department of Computer Engineering


Academic Year:2025-26

CLASS: TE
SEM: V SUBJECT NAME: Theory of Computations (410242)

ASSIGNMENT- 4
Questions: -
1) Design a PDA for accepting a language {a^n b^ 2n | n>=1}

Simulate this PDA for the input string “aaabbbbbb”

2) Design a PDA for accepting a language {0^n 1^m 0^n | m, n>=1}.

Simulate this PDA for the input string “0011100”.

3) Compare FA and PDA

4) Design a PDA for accepting language L= { w c wR | w ∈ (a, b)*}.

5) Define Post machine & Design Post machine for {a^n b^ n | n>=1}

6) Explain any two applications of PDA.

7) Construct a PDA equivalent to the following CFG : S → 0AA, A → 0S | 1S | 0.

8) Construct PDA that accepts a string of balanced parentheses.

You might also like