Linear Bounded Automata Lbas

Linear Bounded Automata
LBAs
1
Linear Bounded Automata (LBAs)
are the same as Turing Machines
with one difference:
The input string tape space

is the only tape space allowed to use
2
Linear Bounded Automaton (LBA)
Input string
[ a b c d e ]
Working space
Left-end Right-end
in tape
marker marker
All computation is done between end markers
3
We define LBA’s as NonDeterministic
Open Problem:
NonDeterministic LBA’s
have same power with
Deterministic LBA’s ?
4
Example languages accepted by LBAs:
n n n
L = {a b c }
n!
L = {a }
LBA’s have more power than NPDA’s
LBA’s have also less power

than Turing Machines
5
The Chomsky Hierarchy
6
Unrestricted Grammars:
Productions
u→v
String of variables String of variables

and terminals and terminals
7
Example unrestricted grammar:
S → aBc
aB → cA
Ac → d
8
Theorem:
A language L is recursively enumerable

if and only if L is generated by an
unrestricted grammar
9
Context-Sensitive Grammars:
Productions
u→v
String of variables String of variables

and terminals and terminals
and: |u| ≤ |v|

10
The language n n n
{a b c }
is context-sensitive:
S → abc | aAbc
Ab → bA
Ac → Bbcc
bB → Bb
aB → aa | aaA
11
Theorem:
A language L is context sensistive
if and only if
L is accepted by a Linear-Bounded automaton
Observation:
There is a language which is context-sensitive
but not recursive
12
The Chomsky Hierarchy
Non-recursively enumerable
Recursively-enumerable
Recursive
Context-sensitive
Context-free
Regular
13
Decidability
14
Consider problems with answer YES or NO
Examples:
• Does Machine M have three states ?
• Is string w a binary number?
• Does DFA M accept any input?
15
A problem is decidable if some Turing machine
decides (solves) the problem
Decidable problems:
• Does Machine M have three states ?
• Is string w a binary number?
• Does DFA M accept any input?
16
The Turing machine that decides (solves)
a problem answers YES or NO
for each instance of the problem
Input YES
problem Turing Machine
instance NO
17
The machine that decides (solves) a problem:
• If the answer is YES

then halts in a yes state
• If the answer is NO
then halts in a no state
These states may not be final states

18
Turing Machine that decides a problem
YES states
NO states
YES and NO states are halting states

19
Difference between
Recursive Languages and Decidable problems
For decidable problems:

The YES states may not be final states
20
Some problems are undecidable:
which means:
there is no Turing Machine that
solves all instances of the problem
A simple undecidable problem:
The membership problem
21
The Membership Problem
Input: •Turing Machine M

•String w
Question: Does M accept w ?
w∈ L(M ) ?
22
Theorem:
The membership problem is undecidable
(there are M and w for which we cannot

decide whether w∈ L(M ) )
Proof: Assume for contradiction that

the membership problem is decidable
23
Thus, there exists a Turing Machine H
that solves the membership problem
M YES M accepts w
H
w NO w
M rejects
24
Let L be a recursively enumerable language
Let M be the Turing Machine that accepts L
We will prove that L is also recursive:
we will describe a Turing machine that

accepts L and halts on any input
25
Turing Machine that accepts L
and halts on any input
M H
YES accept w
M accepts w?
w NO reject w
26
Therefore, L is recursive
Since L is chosen arbitrarily, every

recursively enumerable language is also
recursive
But there are recursively enumerable

languages which are not recursive
Contradiction!!!!
27
Therefore, the membership problem
is undecidable
END OF PROOF
28
Another famous undecidable problem:
The halting problem
29
The Halting Problem
Input: •Turing Machine M

•String w
Question: Does M halt on input w ?
30
Theorem:
The halting problem is undecidable
Proof: Assume for contradiction that

the halting problem is decidable
31
There exists Turing Machine H
that solves the halting problem
M YES M halts on w
H
w NO doesn’t
M w
halt on
32
Let L be a recursively enumerable language
Let M be the Turing Machine that accepts L
We will prove that L is also recursive:
we will describe a Turing machine that

accepts L and halts on any input
33
Turing Machine that accepts L
and halts on any input
M H
NO reject w
M halts on w?
w YES
accept w
Halts on final state
Run M
with input w reject w
Halts on non-final
state
34
Therefore L is recursive
Since L is chosen arbitrarily, every

recursively enumerable language
is also recursive
But there are recursively enumerable

languages which are not recursive
Contradiction!!!!
35
Therefore, the halting problem is undecidable
END OF PROOF
36

Linear Bounded Automata Lbas

Uploaded by

Copyright:

Available Formats

Linear Bounded Automata Lbas

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Linear Bounded Automata Lbas

Uploaded by

Copyright:

Available Formats

Linear Bounded Automata

The input string tape space

All computation is done between end markers

LBA’s have more power than NPDA’s

LBA’s have also less power

String of variables String of variables

A language L is recursively enumerable

String of variables String of variables

and: |u| ≤ |v|

• Is string w a binary number?

• Does DFA M accept any input?

• Is string w a binary number?

• Does DFA M accept any input?

• If the answer is YES

These states may not be final states

YES and NO states are halting states

For decidable problems:

A simple undecidable problem:

The membership problem

Input: •Turing Machine M

Question: Does M accept w ?

(there are M and w for which we cannot

Proof: Assume for contradiction that

Let M be the Turing Machine that accepts L

We will prove that L is also recursive:

we will describe a Turing machine that

Since L is chosen arbitrarily, every

But there are recursively enumerable

The halting problem

Input: •Turing Machine M

Question: Does M halt on input w ?

Proof: Assume for contradiction that

Let M be the Turing Machine that accepts L

We will prove that L is also recursive:

we will describe a Turing machine that

Since L is chosen arbitrarily, every

But there are recursively enumerable

You might also like