5.7 RANDOM-ACCESS MACHINE
A randon access machine is defined as follows:
Data Types: The only data type supported is the Natural Numbers 0, 1, 2, 3,
......... But the numbers may be very large.
Variables: An orbitrary number of variables are allowed. Each variable is
capable of holding a single natural number. All variables are initialized to 0.
Tests: The only test allowed is = 0.
Statements: There are the following types of statements in the language:
(a) if then else ;
(b) while do ;
(c) : = +1; (increment)
(d) : = –1; (decrement)
It is to be noted that decrementing a variable whose value is already zero
has no effect.
Statements to be executed in sequence (; ;
; ...... are allowed and parantheses are used to group a sequence of
statement into a single statement. This language is very equivalent in power to
a Turing machine. This can be proved by using the language to implement a
Turing machine, and then using a Turing machine to enulate the language.
This language is so powerful to compute anything that can be computed in
any programming language.
GLOSSARY
Context sensitive language: Language generated by a context-sensitive
grammar.
Context-sensitive grammar: It is one whose productions are of the form
xAy xVy
→
where A V
∈ and x v y V T
, ,
(
) .
*
∈ ∪
Linear Bounded automata (LBA): It is a TM whose tape is only αn squares
long, where ‘n’ is the length of input string and α is a constant
associated with the LBA.
Chomsky hierarchy: Has 4 types of languages viz.,
(a) Regular language
(b) Context-free language
(c) Context-sensitive language
(d) Recursively enumerable language.
214
Theory of Automata, Formal Languages and Computation