100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Samenvatting Automata and Complexity (X_401049) $7.04
Add to cart

Summary

Samenvatting Automata and Complexity (X_401049)

 81 views  5 purchases
  • Course
  • Institution

Summary of the course Automata & Complexity given at VU University Amsterdam.

Preview 3 out of 28  pages

  • July 12, 2022
  • 28
  • 2021/2022
  • Summary
avatar-seller
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

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

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

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

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 $7.04. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

53022 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$7.04  5x  sold
  • (0)
Add to cart
Added