Taijf 101-120

Klasa automatów ze stosem akceptujących za pomocą stanu akceptującego jest równoważna klasie automatów akceptujących za pomocą jednoczesnego opróżnienia stosu i wejścia.

Klasa automatów ze stosem jest równoważna klasie gramatyk bezkontekstowych.

• Automat ze stosem będzie automatem deterministycznym wtedy i tylko wtedy gdy
• 1) dla każdej konfiguracji będzie określony co najwyżej 1 ruch, gdzie przez konfiguracje rozumiemy nie sprawdzanie symbolu wejściowego.
• 2) jeśli ε-ruch nie prowadzi do odrzucenia wejścia, to wówczas każdy ruch dla tego samego stanu i tego samego symbolu stosu oraz dowolnego symbolu wejściowego prowadzi do odrzucenia wejścia (lub akceptacji).

Automat zaakceptuje dane wejściowe wtedy i tylko wtedy gdy po zakończeniu obliczenia automat wejdzie w stan akceptujący

• A = (Q, Σ, δ, q0, F)
• Q - skończony zbiór stanów,
• Σ - skończony alfabet wejściowy
• δ - funkcja przejścia
• q0 - stan początkowy
• F - zbiór stanów końcowych

δ deterministyczna : Q × Σ → Q

Językiem akceptowanym przez automat skończony deterministyczny nazywamy zbiór słów nad alfabetem Σ, dla których automat kończy obliczenie w stanie akceptującym

• Opisem chwilowym automatu skończonego deterministycznego nazywamy następujący ciąg symboli:
• qα
• q - bieżący stan automatu q ∈ Q
• α - ciąg symboli wejściowych nie wczytanych przez automat

• - sterowanie jest w stanie początkowym q0
• - głowica jest ustawiona nad pierwszą literą słowa wejściowego

Obliczenie automatu - ciąg konfiguracji taki, że pierwszym elementem tego ciągu jest konfiguracja początkowa, a każdy kolejny jest otrzymany z poprzedniego za pomocą funkcji przejścia

• Na podstawie symbolu x czytanego przez głowice oraz na podstawie stanu p, w którym jest sterowanie, następuje wykonanie ruchu zgodnie z zadaną funkcją przejścia, to znaczy:
• - przejście sterowania do pewnego stanu q ∈ Q
• - przesunięcie głowicy o jedną komórkę w prawo.

Ruch automatu polega na zastosowaniu funkcji przejścia dla danej konfiguracji tzn. automat usuwa symbol z wejścia i przechodzi do pewnego stanu.

• A = (Q, Σ, δ, q0, F)
• Q - skończony zbiór stanów,
• Σ - skończony alfabet wejściowy
• δ - funkcja przejścia
• q0 - stan początkowy
• F - zbiór stanów końcowych

• δ niedeterministyczna: Q × Σ → 2^(Q)
• Wartościami funkcji przejścia są podzbiory stanów ( w tym ∅)

Językiem akceptowanym przez automat skończony niedeterministyczny nazywamy zbiór słów nad alfabetem ∑, dla których obliczenie automatu zawiera ścieżkę prowadzącą od korzenia do liścia akceptującego.

• Obliczeniem automatu skończonego niedeterministycznego dla słowa wejściowego w = a(1)a(2)a(3)...a(n) jest drzewo:
• - Którego wierzchołki są etykietowane opisami chwilowymi automatu.
• - Którego korzeń jest etykietowany opisem chwilowym konfiguracji początkowej automatu.
• - Dla którego potomkami dowolnego wierzchołka na wysokości k - 1 są takie wierzchołki na wysokości k, że etykiety wierzchołka i jego potomka pozostają w relacji ruchu |- dla symbolu wejściowego a(k).
• - Liść drzewa obliczenia nazwiemy akceptującym wtedy i tylko wtedy, gdy jest on wierzchołkiem na wysokości n, a stan opisu chwilowego automatu jest stanem akceptującym.

• Opisem chwilowym automatu skończonego niedeterministycznego nazywamy nastepujący ciąg symboli:
• qα
• q - bieżacy stan automatu q ∈ Q
• α - ciąg symboli wejściowych nie wczytanych przez automat

Relacja ruchu automatu skończonego niedeterministycznego jest relacją binarną nad zbiorem opisów chwilowych. gdzie |- jest symbolem tej relacji. Dwa opisy chwilowe będą pozostawać w relacji ruchu wtedy i tylko wtedy, gdy drugi z nich został otrzymany z pierwszego przez wczytanie symbolu z wejścia i przejściu sterowania automatu do stanu należącego do podzbioru stanów wartości funkcji przejścia.

• Obliczenie to ciąg konfiguracji gdzie
• -pierwszym elementem jest konfiguracja początkowa.
• -kolejnym jest konfiguracja otrzymana za pomocą funkcji przejścia
• -ostatnim jest konfiguracja końcowa

Domknięciem funkcji przejścia automatu skończonego deterministycznego nazywamy funkcję

Automat deterministyczny jest szczególnym przypadkiem automatu niedeterministycznego gdzie argumentami wejścia są jednoelementowe zbiory stanów a zbiór stanów akceptujących nie zmienia się

Klasa automatów skończonych deterministycznych jest równoważna klasie automatów skończonych