Quiz 03 (February, 20th)
Statistics
There were 3 problems, each worth 10 points.
- Min: 2
- Median: 23
- Max: 30
Problem 1
Design a PDA with just one state (apart from a 'dead-end' state, which
you will omit) that accepts just those binary strings w, whose prefixes
have at least as many 0's as 1's; i.e., the language of the PDA is
{w | w \in {0,1}* and every prefix of w has at least as many 0's as 1's}.
Thus, e, 0, 00, 01, 000, 001, 010, ... should be accepted, but 1, 10, 11,
011, 100, 101, 110, 111, ... should not.
Solution
Problem 2
Formally state the Pumping Lemma for context-free languages. Here
is the start: For every context-free language L, there exists a
positive integer p such that...
Solution
... for every string s in L such that the length of s is at least p,
s can be written as s = uvxyz such that
- uvixyiz is in L for all nonnegative integers i;
- length of vxy is no greater than p;
- length of vy is greater than 0.
Problem 3
Show the next 4 TM configurations that result from initial configuration
p010, assuming that
- \delta(p,1) = (p,1,L)
- \delta(p,0) = (q,0,R)
- \delta(q,1) = (q,1,R)
- \delta(q,0) = (q,0,R)
Solution
The series of configurations we get is: p010, p110, 0q10, 00q0, 001q.
February, 22nd