Construct a PDA that recognizes the following language:{x\in {a,b}* : #a(x) = #b(x)}Hint: To get the maximum number of points, use as few states and nonterminals as possible!Alphabet: (a, b)o Stack alphabet (the first symbol is the initial one): Z Y Xo Acceptance condition: empty stackDeterministic (DPDA): falseHintsapply+

Answered: Construct a PDA that recognizes the…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Construct a PDA that recognizes the following language:
{x\in {a,b}* : #a(x) = #b(x)}
Hint: To get the maximum number of points, use as few states and nonterminals as possible!
Alphabet: (a, b)
o Stack alphabet (the first symbol is the initial one): Z Y X
o Acceptance condition: empty stack
Deterministic (DPDA): false
Hints
apply
+

Expert Solution

Step 1

PDA for Number of a = Number of b

a) While scanning the input, if 'a' comes first we push it onto the stack.
Also if after 'a', again the letter 'a' comes then push it again.

b) If 'b' comes first, then we push it in the STACK (Assumption -> 'a' did not come in the stack yet)
Similar to previos step, if again 'b' comes then push it in the STACK.

c) Now if 'a' is present at the top of STACK and 'b' comes next then, pop 'a'
Similarily if 'b' is present in top of STACK and 'a' comes next then, pop 'b'

So after the complete string is scanned to the end, if nothing is left in the STACK (empty stack) then we can say that it is accepted by the PDA.

Stack Transitions ->

δ(0, a, Z) = (0, aZ)     
δ(0, a, a) = (0, aa)     
δ(0, b, Z) = (0, bZ)     
δ(0, b, b) = (0, bb)     
δ(0, b, a) = (0, ε)     
δ(0, a, b) = (0, ε)
δ(0, ε, Z) = (1, Z)

Step by step

Solved in 2 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions