Summary
Samenvatting Automata and Complexity (X_401049)
- Module
- Institution
Summary of the course Automata & Complexity given at VU University Amsterdam.
[Show more]
Seller
Follow
lauraduits1
Reviews received
Content preview
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller lauraduits1. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £5.65. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
76669 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now