1 / 13

1 / 13X36DSA 2004 The complexity of different algorithms varies: O(n), Ω(n2), Θ(n·log2(n)), …

Různé algoritmy mají různou složitost: O(n), Ω(n2), Θ(n·log2(n)), …

DSA

Různé algoritmy

mají

různou složitost

2 / 13X36DSA 2004 The complexity of different algorithms varies: O(n), Ω(n2), Θ(n·log2(n)), …


DSA

The complexity

of different algorithms

varies

/ 13X36DSA 2004 The complexity of different algorithms varies: O(n), Ω(n2), Θ(n·log2(n)), …


Abeceda … konečná (neprázdná) množina symbolů |A| … mohutnost abecedy A

A = { ‘A’, ‘D’, ‘G’, ‘O’, ‘U’}, |A| = 5

A = {0,1}, |A| = 2

A = { , , }, |A| = 3

Slovo (nad abecedou A) … konečná (příp. prázdná) také řetězec posloupnost symbolů abecedy (A) |w| … délka slova w

w = OUAGADOUGOU, |w| = 11

w = 1001, |w| = 4

w = , |w| = 5

Příklady:

Příklady:

Abeceda

Slovo

Jazyk



Jazyk

Jazyk … množina slov (=řetězců) (ne nutně konečná, může být prázdná) |L| … mohutnost jazyka L

Jazyk

Specifikace jazyka -- Výčtem všech slov jazyka (jen pro konečný jazyk)

Příklady: A1 = {‘A’, ‘D’, ‘G’, ‘O’, ‘U’}

L1 = {ADA, DOG, GOUDA, D, GAG}, |L1| = 5

A2 = {0,1}

L2 = {0, 1, 00, 01, 10, 11}, |L2| = 6

A3 = { , , }L3 = { , , }, |L2| = 3

1



Specifikace jazyka

-- Volný (ale jednoznačný) popis v přirozeném jazyce (obvykle pro nekonečný jazyk)

Příklady: A1 = {‘A’, ‘D’, ‘G’, ‘O’, ‘U’}L1: Množina všech slov nad A1, která začínají na DA,

končí na G a neobsahují podposloupnost AA. L1 = {DAG, DADG, DAGG, DAOG, DAUG, DADAG, DADDG… }

|L1| =

A2 = {0,1}

L2: Množina všech slov nad A2, která obsahují více 1 než 0

a za každou 0 jsou alespoň dvě 1. L2 = { 1, 11, 011, 0111, 1011, 1111, … , 011011, 011111, … }

|L2| =

2

Jazyk



Specifikace jazyka

-- konečným automatem3

… abeceda … konečná množina symbolů |A| ... mohutnost abecedy... množina stavů (mnohdy očíslovaných) (co je to „stav“ ?) ... přechodová funkce ... σ: QA Q

... počáteční stav S0 Q

… neprázdná množina koncových stavů ≠ QF Q

A Q σ

S0

QF

Konečný automat (finite automaton)

je pětice (A, Q, σ, S0, QF), kde:

Konečný automat



CS A B1

0

0 0

1

0

1 1

D 0,1

… abeceda … {0,1}, |A| = 2... množina stavů {S, A, B, C, D }... přechodová funkce ... σ: QA Q : { σ(S,0) = S, σ(A,0) = B, σ(B,0) = C, σ(C,0) = C, σ(D,0) = D, σ(S,1) = A, σ(A,1) = D, σ(B,1) = D, σ(C,1) = A, σ(D,1) = D } ... počáteční stav S Q… neprázdná množina koncových stavů ≠ { C } Q

A Q σ

S0

QF

Přechodový diagram automatu FA1

Automat FA1:

FA1

Konečný automat

C



S A B1

0

0 0

1

0

1 1

D 0,1

0 1 0 0 0 1 0 0

CS A B1

0

0 0

1

0

1 1

D 0,1

0 1 0 0 0 1 0 0

FA1

FA1

Konečný automat

C



S A B1

0

0 0

1

0

1 1

D 0,1

0 1 0 0 0 1 0 0

CS A B1

0

0 0

1

0

1 1

D 0,1

0 1 0 0 0 1 0 0

FA1

FA1

Konečný automat

C



S A B1

0

0 0

1

0

1 1

D 0,1

0 1 0 0 0 1 0 0

CS A B1

0

0 0

1

0

1 1

D 0,1

0 1 0 0 0 1 0 0

FA1

FA1

Konečný automat

C



S A B1

0

0 0

1

0

1 1

D 0,1

0 1 0 0 0 1 0 0

CS A B1

0

0 0

1

0

1 1

D 0,1

0 1 0 0 0 1 0 0

FA1

FA1

Konečný automat



CS A B1

0

0 0

1

0

1 1

D 0,1

0 1 0 0 0 1 0 0

Po přečtení posledního symbolu je automat FA1 v koncovém stavu

0 1 0 0 0 1 0 0Slovo

je přijímáno automatem FA1

FA1

Konečný automat

C



S A B1

0

0 0

1

0

1 1

D 0,1

CS A B1

0

0 0

1

0

1 1

D 0,1

0 10

0 01

1

1

FA1

FA1

Konečný automat

C



S A B1

0

0 0

1

0

1 1

D 0,1

CS A B1

0

0 0

1

0

1 1

D 0,1

10

0 01

1

1

0

FA1

FA1

FA1

Konečný automat



CS A B1

0

0 0

1

0

1 1

D 0,1

0 101

Po přečtení posledního symbolu je automat FA1 ve stavu, který není koncový

1 0 0 1Slovo

není přijímáno automatem FA1

FA1

Konečný automat

C



S A B1

0

0 0

1

0

1 1

D 0,1

CS A B1

0

0 0

1

0

1 1

D 0,1

0 111 ...

0 111 ...

FA1

FA1

Konečný automat

C



S A B1

0

0 0

1

0

1 1

D 0

CS A B1

0

0 0

1

0

1 1

D 0,1

0 111 ...

0 111 ...

,1

FA1

FA1

Konečný automat



CS A B1

0

0 0

1

0

1 1

D 0,

0 111 ...

1

Žádné slovo začínající

není přijímáno automatem FA1 11 ...

11 ......

01 ...... 1

Žádné slovo obsahující

není přijímáno automatem FA1

není přijímáno automatem FA1Žádné slovo obsahující

Automat FA1 přijímá pouze slova

-- obsahující alespoň jednu jedničku-- obsahující za každou jedničkou alespoň dvě nuly

Jazyk příjímaný automatem = množina všech slov přijímaných automatem

FA1

Konečný automat



Činnost automatu:

Na začátku je automat ve startovním stavu.

Pak čte zadané slovo znak po znaku a přechází

do dalších stavů podle přechodové funkce.

Když dočte slovo, nachází se opět v některém ze svých stavů.

Pokud je v koncovém stavu, řekneme, že dané slovo přijímá,

pokud není v koncovém stavu, řekneme, že dané slovo nepřijímá.

Všechna slova přijímaná automatem tvoří dohromady

jazyk přijímaný (rozpoznávaný) automatem

Konečný automat



Jazyk nad abecedou {0,1} :

Pokud slovo začíná 0, končí 1,pokud slovo začíná 1, končí 0.

(S),0 → (A),1 → (B),0 → (A),1 → (B),0 → (A) 0 1 0 1 0 :

Ukázka analýzy slov automatem FA2:

(A) není koncový stav, slovo 0 1 0 1 0 automat FA2 nepřijímá.

(S),1 → (C),0 → (D),1 → (C),1 → (C),0 → (D) 1 0 1 1 0 :

(D) je koncový stav, slovo 1 0 1 1 0 automat FA2 přijímá.

SA

C

B

D

0

1

01

0

11

0

1

0

Automat FA2

Konečný automat



CS A B0 1 0

1

1 0

D0,1

0,1

Jazyk:{0 1 0,0 1 1 0,0 1 1 1 0,0 1 1 1 1 0,0 1 1 1 1 1 0, ... }

(S),0 → (A),1 → (B),0 → (C),1 → (D),0 → (D) 0 1 0 1 0 :

Ukázka analýzy slov automatem FA3

(D) není koncový stav, slovo 0 1 0 1 0 automat FA3 nepřijímá.

(S),0 → (A),1 → (B),1 → (B),1 → (B),0 → (C) 0 1 1 1 0 :

(C) je koncový stav, slovo 0 1 1 1 0 automat FA3 přijímá.

Automat FA3

Konečný automat



CS A B0 1 0

1

0

0,11

Automat FA4 příjme každé slovo nad abecedou {0,1}obsahující podposloupnost 10 ...... 0

(S),0 → (A),0 → (A),1 → (B),0 → (C),1 → (C) 0 0 1 0 1 :

Ukázka analýzy slov automatem FA4

(S),0 → (A),1 → (B),1 → (S),1 → (S),0 → (A) 0 1 1 1 0 :

(A) není koncový stav, slovo 0 1 1 1 0 automat FA4 nepřijímá.

(C) je koncový stav, slovo 0 0 1 0 1 automat FA4 přijímá.

Automat FA4

Konečný automat



43

5

0 1+,- .

2

0,1,...,9

0,1,...,9 0,1,...,90,1,...,9

0,1,...,9

jakýkoli symbol

+87.09: (0),+ → (1),8 → (2),7 → (2), . → (3),0 → (4),9 → (4)

(0),7 → (2),6 → (2),+ → (5),2 → (5)76+2:

Ukázka analýzy slov

jinak jinakjinakjinakjinak

(4) je koncový stav, slovo +87.05 automat přijímá.

(5) není koncový stav, slovo 76+2 automat nepřijímá.

Jazyk nad abecedou { +, - , . , 0, 1, …, 8, 9, … } jehož slovapředstavují zápis desetinného čísla v desítkové soustavě

Automat FA5

Konečný automat

int isDecimal(int arr[], int length) {int i; int state = 0;

for(i = 0; i < length; i++) { // check each symbol switch (state) { ...



Kód konečného automatu

43

5

0 1+,- .

2

0,1,...,9

0,1,...,9 0,1,...,9

jinak

0,1,...,90,1,...,9

jakýkoli symbol

jinak jinak jinak jinak

FA5

(Čtená posloupnost znaků je uložena v poli arr[ ]):

Implementace konečného automatu

case 0: if ((arr[i] == '+') || (arr[i] == '-')) state = 1; else if ((arr[i] >= '0') && (arr[i] <= '9')) state = 2; else state = 5; break;



43

5

0 1+,- .

2

0,1,...,9

0,1,...,9 0,1,...,9

jinak

0,1,...,90,1,...,9

jakýkoli symbol


FA5


case 1: if ((arr[i] >= '0') && (arr[i] <= '9')) state = 2; else state = 5; break;



43

5

0 1+,- .

2

0,1,...,9

0,1,...,9 0,1,...,9

jinak

0,1,...,90,1,...,9

jakýkoli symbol

jinak jinak jinak jinak FA5


case 2: if ((arr[i] >= '0') && (arr[i] <= '9')) state = 2; else if (arr[i] == '.') state = 3; else state = 5; break;



43

5

0 1+,- .

2

0,1,...,9

0,1,...,9 0,1,...,9

jinak

0,1,...,90,1,...,9

jakýkoli symbol


FA5


case 3: if ((arr[i] >= '0') && (arr[i] <= '9')) state = 4; else state = 5; break; case 4: if ((arr[i] >= '0') && (arr[i] <= '9')) state = 4; else state = 5; break; case 5: break; // no need to react anyhow default : break; } // end of switch



43

5

0 1+,- .

2

0,1,...,9

0,1,...,9 0,1,...,9

jinak

0,1,...,90,1,...,9

jakýkoli symbol


FA5


} // end of for loop -- word has been read

if ((state == 2) || (state == 4)) return 1; // success -- decimal OKelse return 0; // not a decimal

} // end of function isDecimal()



43

5

0 1+,- .

2

0,1,...,9

0,1,...,9 0,1,...,9

jinak

0,1,...,90,1,...,9

jakýkoli symbol


FA5






Regulární jazyk

Jazyk přijímaný nějakým konečným automatem

se nazývá

regulární jazyk



Generativní regulární gramatika

Regulární gramatika:

S → 0AS → 1CA → 0AA → 1BA → 1B → 0AB → 1BB → 1

SA

C

B

D

0

1

01

0

11

0

1

0

C → 0DC → 1CC → 0D → 0DD → 1CD → 0

S → 0A | 1CA → 0A | 1B | 1B → 0A | 1B | 1C → 0D | 1C | 0D → 0D | 1C | 0

Regulární gramatika -- ekvivalentní zápis:



Automat FA2

Specifikace jazyka

4 -- gramatikou




Generování slov pomocí pravidel gramatiky:

S → 0A → 01B → 010A → 0100A → 01001B → 010011

SA

C

B

D

0

1

01

0

11

0

1

0


(1)(2)(3)(4)(5)(6)(7)

B → 1C → 0DC → 1CC → 0D → 0DD → 1CD → 0

S → 0AS → 1CA → 0AA → 1BA → 1B → 0AB → 1B

(8)(9)(10)(11)(12)(13)(14)

(1) (4) (6) (3) (4) (8)

S je startovní symbol, který se pomocí pravidel gramatiky expanduje:

S → 1C → 10D → 100D → 1000 (2) (9) (12) (14)




SA

C

B

D

0

1

01

0

11

0

1

0

S → 0A

Pravidlo gramatiky:

Levá strana Pravá strana

Symboly 0,1, které jsou prvky abecedy výsledného slova se nazývají terminální symboly

Ostatní symboly sloužící k expanzi (S, A, B, C, ...) se nazývají neterminální symboly –ve výsledném slově se nesmí objevit.

V regulární gramatice smí být na levé straně straně každého pravidla jen jediný neterminální symbol, na pravé straně smí být buď jen samotný terminál nebo terminál následovaný neterminálem.



Konečný automat, který příjímá jazyk L, lze převést na gramatiku, která generuje týž jazyk L.

Za každý přechod ze stavu A do stavu B při čtení symbolu x

A Bx

vytvoříme pravidlo A → xB.

Je-li navíc B koncovým stavem,

BAx

přidáme pravidlo A → x.





SA

C

B

D

0

1

01

0

11

0

1

0



Automat FA2

S → 0AS → 1CA → 0AA → 1BA → 1B → 0AB → 1BB → 1

C → 0DC → 1CC → 0D → 0DD → 1CD → 0



Omezení regulárních jazyků

Zdaleka ne každý jazyk je regulární a tudížzdaleka ne každý jazyk může být rozpoznán konečným automatem a tudížzdaleka ne každý jazyk může být generován regulární gramatikou.

Např. jazyk L2 nad abecedou {0,1}, v němž každé slovo obsahujestejný počet jedniček jako nul.

Neformální důvod: Byl by nutný neomezený počet stavů pro zapamatování počtu nul, který by se pak musel porovnávat s počtem jedniček. (Konečný automat není schopen registrovat, kolikrát byl ten který stav navštíven během čtení slova.) Jazyk L2 lze ale generovat gramatikou, která není regulární:S SS | 0S1 | 1S0 | 01 | 10



Domácí úkol

Jazyk: desetinná čísla {0.24, -21.01, 3.1416, 20.000, ... }

<desetinné číslo> <nezáporné číslo> | - <nezáporné číslo><nezáporné číslo> <celá část> <desetinná část> <celá část> <číslice> | <nenula> <celé0><celé0> <číslice> | <číslice> <celé0><desetinná část> . <celé0><číslice> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <nenula> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Tato gramatika není regulární, jazyk, který generuje, však regulární je, navrhněte pro něj konečný automat a napište regulární gramatiku.




1. Data, sex, alkohol

2. Divácky stabilní atrakce

3. Disney's special activities

4. Dlouhodobá sexualní abstinence

5. Don't study algorithms

6. Drsné společenstvo asociálů

7. Družstvo statečných asociálů

Akronym DSA (3b.!) – uzávěrka

Došlé příspěvky v abecedním pořadí:

Date post:	25-Jan-2016
Category:	Documents
Upload:	baylee
View:	40 times
Download:	0 times

1 / 13

Documents