Samenvatting Automata and Complexity (X_401049)

Automata & Complexity
Introduction
computers are based on a universal computing mechanism

( ie ,
roughly speaking ,
no other computational model can


compute more ) the basic mathematical principles
,




the operations it can to
execute are
strong enough
compute anything computable
However ,
there are certain limits to what is
computable !

in
Turing machines were invented 1936 by Alan
Turing :



-
abstract computation model 011 R

-
automata with read / write tape

9-0 9-
computation
'
-
universal mechanism

limitation of
we can
study the
012 R

modern computers by studying Turing machines .




different kinds of automata for different applications :

finite automata
give rise to
regular languages :




application :
pattern recognising
•




equivalent to :
regular expressions
-




pushdown automata free languages
give rise to context :
-




-



application :
parsing ( e.g .
.
programming languages )
a


equivalent to : context -
free
grammars


turing machines
yield recursively enumerable languages :




application general computation
-
:




↳ form of
strongest automata




depending on the application in mind , you should choose

the appropriate form of automata !

, what can a computer do ?
some problems undecidable (e. termination )
are g. , program
-




-
some problems ( NP -
hard problems ) are (probably) not
efficiently
solvable by a computer leg .
, travelling salesman problems



aspects of
languages :



the form of words in the ( course)
syntax
the
language ← this
-
:




semantics : the meaning of the words in the
language
-




Words & Languages
Words
word =
finite sequence of symbols from an alphabet E
↳
symbols : A, b, C , . . .




↳ words :
v.v , W , ✗ 2
,
y .




↳ E from the alphabet E
a E means a is a
symbol
I !=
"
write ✗ for ( alphabet
"

the word letter in the
we
empty


Everything stored on a computer is a word (a
sequence of bits ) .




so, in particular ,
a computer program is a word .
From an

abstract view ,
a
program
:




-
takes words as input
-


produces a word as output



operations on words
-

concatenation :




if V =
a, . . -

an and W =
bi . . .
bm ,
then VW =
011 . . -
an bi ' ' '
bm

the concatenation of aab and ba is Gabba




length :
-




if ✓ =
9, . . -
an ,
then I V1 = h .




The
length defined 1×1=0 & Nat I V1 1-
can be
inductively 1
: =




the length of abbba is labbba 1=5

, power
- :




the power vk consists of K concatenationS Of v 'S :



"t '

v0 = ✗ & ✓ = vkv

then W2
'

let W =
aba ,
W0 =
✗ ,
W =
aba ,
=
☐baaba

>
and W =
abaabaaba



-
reverse


the of is Cai an IR
=
reverse a, . . -

an . . .
an - . .
a,

R
the reverse can be inductively defined : ✗ = ✗ & ( ✓a)R =
a CVR )
"
the reverse of abcb is Cabcb) =
bcba



Languages
A formal language is a set of words .




E* is
*
A (format L is of LEE
)
language a subset , that
*
[ is the set of all words over E

E ab ,
aab ,
bbaaabb 3 is a finite
language over E =
{ a ,b3



operations on
languages
-

set operations
a language is a set of words .
So the usual set operations
have meaning for languages :
E, E ,
n ,
U, I . . . .




ba C- { a. aba.ba 3 ab ¢ {a ,
aba.ba 3
{ a. ba3 E E a, aba.ba 3 { a. B3 4EA , aba.ba 3
{ a. aba.ba 3 n { a , ab.ba 3 =
{ a .ba 3

{ a. aba.ba 3 U { a. ab.ba 3 =
{ a. ab aba.ba } ,




E a. aba.ba 3 I [ a. ab.ba 3 =
{ aba3



-


complement
The complement [ is all words that are not in the
language L:
*
[ =
[ 1L
for E =
EA3 and L= [ a. aaa 3 .
Then I =
{ ✗ AA3W [ an 1h24 3
,




-
reverse

the is LR { R
I EL3
reverse of language
=
a ✗ ✗


the reverse of L= EX ab , ,
bbaba 3 is LR =
{ t.ba .
ababb 3