date: 2024-11-27
title: "TOC-As-3"
status: DONE
author:
- AllenYGY
tags:
- Assignment
- TOC
publish: True
TOC-As-3
Let
Assume L is context-free.
Let
And
Suppose
By the pumping lemma,
Because
Thus
Therefore
Which means
Therefore
Therefore L is not context-free.
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 0
s representing
The second part, after the separator #
, will contain a sequence of 10
s representing
For example:
000#00
represents 0
(positive result).00#000
represents -0
(negative result).