TOC-As-3

1. Construct NPDA’s that recognize the following languages over . (10 pt for each)

a.

1-a

b.

1-b

c.

1-c

2. Show that the language is not contexr-free.

Let

Assume L is context-free.

Let which is a string in .

And

Suppose , ,,, and

By the pumping lemma,

Because and

Thus

Therefore should at least be

Which means which is a contradiction.

Therefore is not in L.

Therefore L is not context-free.

3. Convert the following grammar to an NPDA. (8pt)

3

4. Let . Design a (nondeterministic) TM for each following language. (10 pt each)

a.

4-a

b.

4-b

c.

4-c

d.

4-d

5. Design a TM for each integer subtraction: for . You need to clearly how the input and the side effect are encoded. (8pt each)

Let

  • Use 0 to represent positive numbers in the unary system.

  • Use # as a separator between the two numbers.

  • Use - as a special marker to indicate a negative result when .

  • Use x as a symbol to do the subtraction.

    Input Format

  • The first part of the tape will consist of a sequence of 0s representing .

  • The second part, after the separator #, will contain a sequence of 10s representing .

For example:

  • 000#00 represents , should be output as 0 (positive result).
  • 00#000 represents , and should be output as -0 (negative result).

5

6. Let Design a which decides whether the symbol is on the tape. (8pt)

6