date: 2024-11-27
title: "TOC-As-3"
status: DONE
author:
  - AllenYGY
tags:
  - Assignment
  - TOC
publish: True

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)

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).