California State University, San Marcos
CS 421
CS421 - Krell – HW3C (based on Week 11 and week12a) -- PDA
=================================================================
DUE: Week 12 Friday April 17, before midnight (11:55)
TOTAL: 30 pts
unknown
===================================================================
------------------------------------------
...[Show More]
CS421 - Krell – HW3C (based on Week 11 and week12a) -- PDA
=================================================================
DUE: Week 12 Friday April 17, before midnight (11:55)
TOTAL: 30 pts
unknown
===================================================================
-------------------------------------------------------
PDA Problem [2pts per problem = 26 pts]
----------------------------------------------------------
1) The language is { (a | b)^n c (a | b)^n | n>=1 }
abab c baba
aaaa c bbbb
Note that the left side and the right side of c need not be
identical. But the lengths of the left and the right side
must be the same.
Start in q0 with Z on the stack. (assumed)
a) Idea: Stay in q0 up to c,
pushing X for a and b as they are read.
Give the 4 Trs's here for all such valid cases:
Trs(q0, a, Z) = (q0, XZ)
Trs(q0,b,Z) = (q0, XZ)
Trs(q0,b,X) = (q0, XX)
Trs(q0,a, X) = (q0, XX)
b) Idea: If c is seen switch to q1. No change to the stack.
Give the Trs here (hint? What is on the stack?):
Trs(q0, a, X) = (q1, X)
c) Idea: In q1, as a's and b's are read, pop off X's.
Give the 2 Trs's here for all such valid cases:
Trs(q1, a , X) = (q1, epsilon)
Trs(q1, b, X) = (q1, epsilon)
The above Trs’s are not enough. We can finish in two different ways as you see below.
[Show Less]
Access Full Document
Instant download after payment
Card Payments
₿
Crypto Accepted