W dzisiejszej erze technologicznej, zarówno w dziedzinie sprzętu, jak i oprogramowania, nastąpił ogromny rozwój. Jeden z głównych obszarów rozwoju dotyczył metod projektowania sprzętu. Dzięki rozwijająca się technologia , koncepcja wspólnego projektowania sprzętu i oprogramowania była możliwa do wdrożenia. Opracowywane są różne metody, dzięki którym za pomocą oprogramowania można w pełni projektować i symulować systemy sprzętowe. Jedną z takich metod jest teoria automatów. Teoria automatów jest gałęzią Informatyka który zajmuje się projektowaniem abstrakcyjnego modelu urządzeń komputerowych, które automatycznie wykonują określoną sekwencję kroków. W tym artykule omówiono krótkie informacje o samouczku dotyczącym automatów.
Co to jest teoria automatów?
Słowo Automata pochodzi od greckiego, co oznacza „samoczynne działanie”. Automat to matematyczny model maszyny. Automaton składa się ze stanów i przejść. Gdy wejście jest podane do automatu, następuje przejście do następnego stanu, w zależności od funkcji przejścia. Dane wejściowe funkcji przejścia to obecny stan i ostatnie symbole. Jeśli automat ma skończoną liczbę stanów, jest znany jako automaty skończone lub Maszyna skończona . Automaty skończone są reprezentowane przez 5-krotkę (Q, ∑, δ, qo, F)
Gdzie,
Q = skończony zbiór stanów.
∑ = skończony zbiór symboli nazywany również alfabetem automatów.
δ = funkcja przejścia.
qo = stan początkowy wejścia.
F = zbiór stanów końcowych Q.
Podstawowe terminologie teorii automatów
Niektóre z podstawowych terminologii teorii automatów to:
1 . Alfabet : Każdy skończony zbiór symboli w teorii automatów jest znany jako Alfabet. Reprezentowany przez literę zbiór {a, b, c, d, e,} nazywany jest zestawem alfabetu, natomiast litery zestawu „a”, „b”, „c”, „d”, „e” nazywane są symbolika.
dwa . Strunowy : W automatach ciąg jest skończoną sekwencją symboli pobranych ze zbioru alfabetu ∑, Na przykład ciąg S = „adeaddadc” jest prawidłowy na zestawie alfabetu∑ = {a, b, c, d, e,}.
3 . Długość sznurka : Liczba symboli obecnych w ciągu jest określana jako długość ciągu. Dla łańcucha S = „adaada” długość ciągu wynosi | S | = 6. Jeśli długość łańcucha wynosi 0, nazywa się go pustym łańcuchem.
4 . Kleen Star : Jest to operator jednoargumentowy na zbiorze symboli Σ, który daje nieskończony zbiór wszystkich możliwych ciągów, w tym λ, o wszystkich możliwych długościach w zbiorze Σ. Jest reprezentowany przez. Na przykład dla zbioru Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Zamknięcie Kleen : Jest to nieskończony zbiór wszystkich możliwych ciągów alfabetu z wyłączeniem λ. Jest oznaczony. Dla zbioru Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 . Język : Język jest podzbiorem zestawu gwiazdek Kleene∑ * dla niektórych zestawów alfabetu Σ. Język może być skończony lub nieskończony. Na przykład, jeśli język przyjmuje wszystkie możliwe ciągi o długości 2 przez zbiór Σ = {a, d}, to L = {aa, ad, da, dd}.
Języki formalne i automaty
W teorii automatów język formalny to zbiór ciągów, w których znajduje się każdy ciąg składa się z symboli należący do skończonego zestawu Alphabet Σ. Rozważmy język kota, który może zawierać dowolne ciągi z poniższego nieskończonego zestawu…
miauczenie!
mew!
mewww !! ……
Alfabet ustawiony dla języka kota to Σ = {m, e, w,!}. Niech ten zestaw będzie używany dla skończonych automatów stanowych Model-m. Następnie język formalny scharakteryzowany przez model m oznaczany jest przez
L (m)
L (m) = {„miaucz!”, „Miaucz!”, „Mewww”, ……}
Automaton jest przydatny do definiowania języka, ponieważ może wyrazić nieskończony zbiór w postaci zamkniętej. Języki formalne nie są tym samym, co języki naturalne, którymi posługujemy się na co dzień. Język formalny może oznaczać różne stany maszyny, w przeciwieństwie do naszych zwykłych języków. Język formalny służy do modelowania części języka naturalnego, np. Składni itp. Języki formalne są definiowane przez automaty skończone. Istnieją dwie główne perspektywy automatów skończonych - akceptory, które mogą stwierdzić, czy ciąg jest w języku, a druga to generator, który produkuje tylko łańcuchy w języku.
Deterministyczne automaty skończone
W deterministycznym typie automatów, gdy dane wejściowe są podane, zawsze możemy określić, do jakiego stanu nastąpi przejście. Ponieważ jest to automat skończony, nazywa się to deterministycznymi automatami skończonymi.
Reprezentacja graficzna
Diagram stanów to digrafy używane do graficznej reprezentacji deterministycznych automatów skończonych. Rozumiemy na przykładzie. Niech deterministyczne automaty skończone będą…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} a funkcja przejścia be
Forma tabelaryczna reprezentacji graficznej
Diagram stanu
Diagram stanów deterministycznych automatów skończonych
Ze schematu stanu
- Stany są reprezentowane przez wierzchołki.
- Przejścia są reprezentowane przez łuk oznaczony alfabetem wejściowym.
- Pusty pojedynczy łuk wejściowy reprezentuje stan początkowy.
- Stan z podwójnymi okręgami jest stanem końcowym.
Niedeterministyczne automaty skończone
Automaty, w których nie można określić stanu wyjściowego dla danego wejścia, nazywane są automatami niedeterministycznymi. Jest również nazywany niedeterministycznymi automatami skończonymi, ponieważ ma skończoną liczbę stanów. Niedeterministyczne automaty skończone są reprezentowane jako zbiór 5-krotny gdzie (Q, ∑, δ, qo, F)
Q = skończony zbiór stanów.
∑ = Zestaw alfabetu.
δ = funkcja przejścia
gdzie : 
qo = Stan początkowy.
Reprezentacja graficzna
Niedeterministyczne automaty skończone są przedstawiane za pomocą diagramu stanów. Niech niedeterministyczne automaty skończone będą-
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Przejścia są
Forma tabelaryczna reprezentacji graficznej
Diagram stanu
Diagram stanów niedeterministycznych automatów skończonych
Aplikacje teorii automatów
Aplikacje teoria automatów obejmują następujące elementy.
- Teoria automatów jest bardzo przydatna w dziedzinie teorii obliczeń, produkcji kompilatorów, sztucznej inteligencji itp.
- W przypadku kompilatorów przetwarzania tekstu i projektów sprzętu automaty skończone odgrywają główną rolę.
- Do zastosowań w AI i w języki programowania Gramatyka bezkontekstowa jest bardzo przydatna.
- W dziedzinie biologii przydatne są automaty komórkowe.
- W teorii ciał skończonych możemy również znaleźć zastosowanie automatów.
W tym artykule poznaliśmy krótkie wprowadzenie do języków teorii automatów i obliczeń. Automaty istnieją od czasów prehistorycznych. Wraz z wynalezieniem nowych technologii w tej dziedzinie widać wiele nowych osiągnięć. Z jakim typem automatów się spotkałeś?
