Question

Construct a Pushdown automaton that accepts the strings on alphabet {a,b,(, ) }, where parenthesis “(””)” matched in pairs. For example strings “((ab))”,”(a)b()” are in the language, while “((”,”(ab))” are not. Please determine if your PDA deterministic or nondeterministic. (With Proper Steps and explanation)

PLEASE DO NOT COPY PASTE THE ANSWER FROM OTHER SOLUTIONS, AND PROVIDE PROPER EXPLANATION AND STEPS.

Answer 1

( ), (( )), ( )( ) are the examples of valid pairs of parenthesis which are supposed to the accepted by the PDA we are meant to create.
), (, ( )), ( )( are the examples of invalid pairs of parenthesis which are supposed to be rejected.

Here is the reuired PDA according to the requirements specified in the question.


The PDA shown above is deterministic because every state is having a transaction on every input. In the PDA given above,

b.cc acle ciclcc C, 2/C20 (20/20 9,51€ (le Ecce ade b, cic a. 20/20 9,20/20 b. 20/20 720/20 (2 e zdro ), 2010 a 20/20 birolo

• q₀, q₁, q₂, q₃ are the state in which q₃ is the rejecting state. If top of the stack is Z₀ and ')' is the input, then it will be rejected.
• State q₂ is the final state. If the top of the stack is Z₀ and there is no input then the string will be accepted.

Here, we are not making transaction to another state on seeing 'a' and 'b' because here we only need to concern about the parenthesis. This is what we are doing here:

• We are assuming that initially, the top of the stack is containing Z₀.
• We are pushing every '(' into the stack. And for every input of 'a' and 'b', we are staying on the same state.
• Then we will pop one '(' for every input of ')'. Again for every input of 'a' and 'b', we are staying on the same state.
• At the end, if Z₀ is on top of the stack, then the input string is accepted otherwise not.

The transition functions are as follows.

8690,(,0) 80%,2,2)=(2, 2) 8C%, C, Z) = Clo, cz.) Clo,CC) SC4, a. C) = (to, e) Scr, b, c) = (2,0) SClo, a, 2o) (2012) 8C%0.6, 2.) = (2, 2) - . SC4,7,9) (2,6) 8(9,2,0) =(4,() Sea, b, c) C4,C) SCU,(,0) (&o, () 8C1,,,Z) - Cis, z.) 8C93,6,2) (23, 20) SCP, 720) (93,2o) SCL, a, ro) (220) SC23, 6, 20) = (93120) 869, , 2) = (1,7) a string accepted. -

b.cc acle ciclcc C, 2/C20 (20/20 9,51€ (le Ecce ade b, cic a. 20/20 9,20/20 b. 20/20 720/20 (2 e zdro ), 2010 a 20/20 birolo

8690,(,0) 80%,2,2)=(2, 2) 8C%, C, Z) = Clo, cz.) Clo,CC) SC4, a. C) = (to, e) Scr, b, c) = (2,0) SClo, a, 2o) (2012) 8C%0.6, 2.) = (2, 2) - . SC4,7,9) (2,6) 8(9,2,0) =(4,() Sea, b, c) C4,C) SCU,(,0) (&o, () 8C1,,,Z) - Cis, z.) 8C93,6,2) (23, 20) SCP, 720) (93,2o) SCL, a, ro) (220) SC23, 6, 20) = (93120) 869, , 2) = (1,7) a string accepted. -

Answer 2

),B12 bala Pushing open brackets -B's popping each B for each ) Doing nothing over as & b's 9,2/a 5,2/B P DA is non- deterministic PDA accepts by empty stack.

Answer 3

Constructed PDA in the image below

where each transition is a,b;c

a = input symbol

b = pop from stack (stack symbol)

c = push to stack

Also, Z is initial stack symbol and pushed into the stack from the beginning of automation.

This PDA is deterministic because there is only one transition for each pair of input symbol and stack symbol.

push Down Auto mata Alphabet : {a,b,(,)] ) (5),(10) (C,C1(c) (6,2/C2) Of lo (€, 2/2) (a, z/z) (b, z/z) (a, (l() (bil1c) Non PDA is Dete eministica do is is initial state &t is Final state

Answer 4

push Down Auto mata Alphabet : {a,b,(,)] ) (5),(10) (C,C1(c) (6,2/C2) Of lo (€, 2/2) (a, z/z) (b, z/z) (a, (l() (bil1c) Non PDA is Dete eministica do is is initial state &t is Final state