Lekce - Automaty a regularní výrazy

Evropská unieEvropský sociální fondPraha & EU: Investujeme do vaší budoucnosti

Automat

Hrací skřínka, Leopold Aucac Aine, Paris

Řídicí automat typu Moore

M = < X, S=Sz ∪ Sm, Z, ω, δ, S0 >

ZN

ásle

dujíc

í st

av S

*Sm

Sz

Sm*

Sz*

Sm

Sz

δ

Paměť

ω

Xt

Vzorkování,měření vstupů

Zápis výstupů

X

vnitřní proměnné automatu

X

Zt

Definice konečného automatuFSM – Finite State Machine

δ - přechodová funkce - zobrazení δ: X x S -> S ω - výstupní funkce - zobrazení ω:

ω: S -> Z (Moore) ω: X x S -> Z (Mealy)

X - konečná množina všech vstupních vektorů Z - konečná množina všech výstupních vektorů S - konečná množina všech vnitřních stavů

Uspořádaná šestice

M = < X, S, Z, ω, δ, s0 >

s0 - počáteční stav S0 S

Příklad: Synchronní kódový zámek

Odemkne, pokud vstup začíná: 0011, jinak ne. Generuje výstup A (Accepted=přijato) ve stavu Q5

Takový automat se někdy nazývá konečný akceptor, nebo rozpoznávací či klasifikační automat (Finite State Acceptor or Acceptor Finite State Machine)

0

Q1

1

Q1

Q2

Q3

Q4

A

100

QE

11 0

0,1AcceptedStart

Příklad2: Synchronní kódový zámek

Chceme nyní odemknout, pokud vstupní posloupnost začíná 00 a končí 11

10

0 0

0

1A B C D E

Příklad: Synchronní kódový zámek

NFA – Nondeterministic Finite Automat/Acceptor

DFA – Deterministic Finite Automat/Acceptor

0 1

0 0

0

1A B C D E

0, 10 0 11

Nedeterministický přechod

A B C D E

NFA- animace 1/2

NFA – Nondeterministic Finite Automat/Acceptor

0, 10 0 11

Nedeterministický přechod

A B C D E

0 0 1 0 1 1

backtracking

stackstack

NFA – animace 2/2

NFA – Nondeterministic Finite Automat/Acceptor

0, 10 0 11

Nedeterministický přechod

A B C D E

0 0 1 0 1 1

stack

Accepted

Nedeterministické chování není náhodné

Deterministické:f(1) → 1 vždy

Náhodné:f(1) → 1 v 50% případů,f(1) → 2 v ostatních situacích

Nedeterministické chováníf(1) → 1 nebo f(1) → 2, ale nepovíme, kdy tomu tak bude.

Nedeterministické chování může vypadat deterministicky, náhodně, nebo i hůře

Definice konečného akceptoru

δ - přechodová funkce pro DFA - zobrazení δ: X x S -> S pro NFA – zobrazení δ: {X + ε} x S -> množina S,

kde ε je prázdný vstup

X - konečná množina všech vstupních vektorů S - konečná množina všech vnitřních stavů

Uspořádaná pětice

M = < X, S, δ, s0, F >

s0 - počáteční stav s0 S

F – množina (i prázdná) koncových stavů F S

DFA versus NFA

NFA se dají mnohem rychleji sestavit, ale obtížněji se prochází jejich stavovým diagramem – musíme si pamatovat stavy a případně se vracet.

NFA s více koncovými stavy lze vždy převést na NFA s jedním koncovým stavem.

NFA lze vždy převést na DFA, ale odpovídající DFA reprezentace může mít exponenciální nárůst počtu stavů nebo přechodů.

Jakákoliv posloupnost a b končící a b

A B Ca b

a,b

A A,Ba b

b

A,C

ab

a

NFA

DFA

NFA a DFA

Jazyky

The Tower of Babel, Pieter Brueghel, c. 1563, Kunsthistorisches Museum, Vienna

Automaty rozpoznávají jazyk

Abeceda (Alphabet) – konečná množina znaků

Slovo (String) – konečná posloupnost znaku – může být prázdná , (prázdné slovo se v některých textech označuje i jako )

Jazyk (Language) – množina, případně i nekonečná, všech slov utvořených z abecedy – množina může být i prázdný { }, tj. prázdný jazyk.

Příklady jazyků

Předpokládejme = {a, b, c}, pak lze z utvořit například jazyky:

{aa,ab,ac,bb,bc,cc} {ab,abc,abcc,abccc,. . .} { } { } {a, b, c,

Regulární jazyky

Regulární jazyky jsou jazyky rozpoznávané pomocí NFA nebo DFA.

Akceptory, které rozpoznávají regulární jazyky, se popisují regulárními výrazy.

Java, PHP, Python, C# a další, implementují regulární výrazy zpravidla pomocí NFA, která se dá rychleji sestavit.

Příklady jazyků a jejich DFA

baL n1

baL 2

a

b

ab

1M

2M

Sjednocení (Union) jazyků

1M

2M

21 LL

Příklad sjednocení

a

b

ab

baL n1

baL 2

abbaLL n ,21

Spojení (Concatenation)

21LL

1M 2M

Příklad spojení

a

b ab

baL n1 baL 2

bbaababaLL nn 21

Operace * (Kleene star)

*1L

1M

Příklad *

*1* baL n

a

b

baL n1

Příklad na doplněk jazyka

a

b ba,

ba, baL n

a

b ba,

ba, baL n

Fneg = S-F , slovy: invertujeme koncové stavy

Regulární výrazy

http://www.dotnetcoders.com/web/Learning/Regex/default.aspx

Příklad: Automat → regulární výraz 1/5

a

1 2 3 4 5

6 7

d bc

d0

d a

d bbc

1 2 3 4 5

6 7

d [abc] d0

d a

d b[bc]

[abc] - jeden znak ze seznamu znaků. V uvedeném příkladu jde o znak a nebo b nebo c.

Příklad: Automat → regulární výraz 2/5

1 2 3 4 5

6 7

d [abc] d0

d a

d b[bc]

3 4 5d[abc]d d

0a

b[bc]d

Příklad: Automat → regulární výraz 3/5

3 4 5d[abc]d d

0a

b[bc]d

b(b|c)da

3 4 5d[abc]d d

0a

b[bc]da

Příklad: Automat → regulární výraz 4/5

3 4 5d[abc]d d

0a

b[bc]da

3 4 5

d[abc]d0

a (b[bc]da)*d

Příklad: Automat → regulární výraz 5/5

50

d[abc]da(b[bc]da)*d

3 4 5

d[abc]d0

a (b[bc]da)*d

* - 0 nebo více znaků ze seznamu. V uvedeném příkladu jde o skupinu (b[bc]da)

Neregulární jazyky

Pro neregulární jazyky nelze navrhnout NFA nebo DFA. Nelze je ani popsat regulárním výrazem.

Příklad: jazyk W = {anbn | n>0}

Regulární výrazy: Metacharacters

Začátečníkům pomůže knihovna regulárních výrazů http://regexlib.com/

Některé "character-class" metacharacters \d – libovolné číslo \D – nečíselný znak \w – libovolný znak slova \W – neslovní znak \s – oddělovač "whitespace" \S – není "whitespace"

Příklad \d\d\d\s\d\d\d\s nalezne: nalezne: ""123 123 456456""

Některé uživatelské znaky

. Jeden znak s výjimkou konce řádku "newline". Např. a.a určuje aea, aia, aca, and a a

[XY] Jeden znak ze seznamu znaků. V uvedeném příkladu jde o znak X nebo Y

[A-Z] Jeden znak z rozsahu od A do Z (v příkladu pouze velká písmena).

[A-Za-z] Jeden znak, malá nebo velká písmena A až Z

[^AB] Jeden znak různý od A nebo B

Modifikátory výrazu

\ Následující znak je literal, ne "metacharacter"

^ Následující výraz se musí se objevit na začátku textu

$ Následující výraz se musí objevit na konci textu

"^Kolo" nalezne "Kolohnát", ale nikoliv "Moje Kolo""stroj$" matches "Nástroj", ale ne "stroje"

Kvantifikátory

* Určuje 0 or více výskytů předchozího

+ Určuje 1 or více výskytů předchozího

? Určuje 0 or 1 výskytů předchozího

{n} Určuje přesně n výskytů předchozího

{n,} Určuje nejméně n výskytů

{n,m} Určuje nejméně n, ale maximálně m výskytů

() Označení skupiny pro kvantifikátor, chceme-li, aby se vztahoval na více prvků

Jaká je správná odpověď?

Ukázka programu v |Javaimport java.util.regex.Matcher;import java.util.regex.Pattern;public class DateMatcher{ public DateMatcher()  {    String aDate = "date: 12-15-2003"; Pattern datePattern = Pattern.compile(

"date: (\\d{2})-(\\d{2})-(\\d{4})");   Matcher dateMatcher = datePattern.matcher(aDate);    if (dateMatcher.find())    {      System.out.println("Month is: " + dateMatcher.group(1));      System.out.println("Day is: " + dateMatcher.group(2));      System.out.println("Year is: " + dateMatcher.group(3));    }  }

  public static void main(String[] args) {    new DateMatcher(); }}

Podmnožinu regulárních výrazů umí i MS-Word

Regulární výrazy se skrývají pod zástupnými znaky

Nabídku operátorů najdete pod Speciální