Quiz 03 (February, 20th)

Statistics

There were 3 problems, each worth 10 points.

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

Problem 3

Show the next 4 TM configurations that result from initial configuration p010, assuming that

Solution

The series of configurations we get is: p010, p110, 0q10, 00q0, 001q.
February, 22nd