Samenvatting
Samenvatting Automata and Complexity (X_401049)
Samenvatting van het vak Automata & Complexity als gegeven aan de Vrije Universiteit Amsterdam.
[Meer zien]Voorbeeld 3 van de 28 pagina's
Voorbeeld 3 van de 28 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
Automata & ComplexityIntroduction
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper lauraduits1. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €6,57. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 53068 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen