The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
48 views

asked in Theory of Computation by (87 points)
edited by | 48 views
+1

because of $\Gamma (Z,a)$. as only stack alphabet.

you have one top of stack alphabet(Z) and one simple stack alphabet(a), now you can not use Z other than top of stack, and you are left with only 'a' for comparisons,

here with 'a' as only comparing parameter-> "you can compare quantity but not quality"

now, for anbn, you need to compare only quantity i.e no. of a's = no. of b's

but for wwr or w#wr, you need to compare corresponding pairs in left half and right half i.e 'a' with 'a' and 'b' with 'b' which require comparison of both quantity and quality which cant be performed with above PDA,

so answer is option 3 only

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
asked Oct 30, 2017 in Mathematical Logic by hem chandra joshi Active (4.5k points) | 52 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,733 questions
47,461 answers
145,522 comments
62,224 users