In het huidige technologische tijdperk hebben zowel hardware als software een enorme ontwikkeling doorgemaakt. Een van de belangrijkste ontwikkelingsgebieden was te zien in de methoden van hardware-ontwerpen. Met de groeiende technologie was het concept van Hardware - Software co-design mogelijk om te implementeren. Er worden verschillende methoden ontwikkeld waarmee, met behulp van software men kan de hardwaresystemen volledig ontwerpen en simuleren. Een van die methoden is de Automata Theory. Automata-theorie is de tak van computertechnologie dat zich bezighoudt met het ontwerpen van het abstracte model van computerapparatuur die automatisch de vooraf bepaalde reeks stappen volgt. Dit artikel bespreekt korte informatie over zelfstudie over automaten.
Wat is automaattheorie?
Het woord Automata is afgeleid van het Grieks, wat 'zelfwerkend' betekent. Een automaat is een wiskundig model van de machine. Automaat bestaat uit toestanden en overgangen. Aangezien de invoer wordt gegeven aan de automaat, maakt deze een overgang naar de volgende toestand, afhankelijk van de overgangsfunctie. De invoer voor de overgangsfunctie zijn huidige toestand en recente symbolen. Als een automaat een eindig aantal toestanden heeft, staat deze bekend als eindige automaten of Eindigetoestandsautomaat De eindige automaten worden weergegeven door een 5-tupel (Q, ∑, δ, qo, F)
Waar,
Q = Eindige reeks toestanden.
∑ = eindige reeks symbolen ook wel Alfabet van de automaten genoemd.
δ = de overgangsfunctie.
qo = begintoestand van de invoer.
F = set van eindtoestanden van Q.
Basisterminologieën van automaattheorie
Enkele van de basisterminologieën van Automata Theory zijn-
1 Alfabet : Elke eindige set symbolen in de automaattheorie staat bekend als het alfabet. Vertegenwoordigd door de letter∑ wordt de reeks {a, b, c, d, e,} Alfabetreeks genoemd, terwijl de letters van reeks 'a', 'b', 'c', 'd', 'e' worden genoemd symbolen.
twee Draad : In automaten is een tekenreeks een eindige reeks symbolen uit de alfabetreeks ∑. De tekenreeks S = ‘adeaddadc’ is bijvoorbeeld geldig voor de alfabetreeks∑ = {a, b, c, d, e,}.
3 Lengte van de snaar : Het aantal symbolen in de tekenreeks staat bekend als de lengte van de tekenreeks. Voor de string S = ‘adaada’ is de lengte van de string | S | = 6. Als de lengte van de string 0 is, wordt het een lege string genoemd.
4 Kleen Star : Het is de unaire operator op de set symbolen Σ, die de oneindige set van alle mogelijke strings geeft, inclusief λ, van alle mogelijke lengtes over de set Σ. Het vertegenwoordigd door. Bijvoorbeeld voor de verzameling Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 Kleen sluiting : Het is de oneindige reeks van alle mogelijke strings van de alfabetreeks exclusief λ. Het wordt aangeduid met. Voor de verzameling Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 Taal : Taal is de subset van de Kleene-sterrenset∑ * voor sommige Alphabet-sets Σ. Taal kan eindig of oneindig zijn. Als een taal bijvoorbeeld alle mogelijke strings van lengte 2 over de set Σ = {a, d} neemt, dan L = {aa, ad, da, dd}.
Formele talen en automaten
In de automaattheorie is formele taal een reeks snaren, waarbij elke snaar is samengesteld uit symbolen behorende tot de eindige alfabetreeks Σ. Laten we eens kijken naar een kattentaal, die alle tekenreeksen uit de onderstaande oneindige reeks kan bevatten ...
miauw!
miauw!
mewww !! ……
Het alfabet dat is ingesteld voor kattentaal is Σ = {m, e, w,!}. Laat deze set worden gebruikt voor een Finite State Automata Model-m. Vervolgens wordt de formele taal die wordt gekenmerkt door het model m aangeduid met
L (m)
L (m) = {‘mew!’, ‘Meww!’, ‘Mewww’, ……}
Automaat is handig voor het definiëren van een taal omdat het een oneindige verzameling in een gesloten vorm kan uitdrukken. Formele talen zijn niet hetzelfde als de natuurlijke talen die we in ons dagelijks leven spreken. Een formele taal kan de verschillende toestanden van de machine aangeven, in tegenstelling tot onze reguliere talen. Formele taal wordt gebruikt om een deel van de natuurlijke taal te modelleren, zoals syntaxis enz. Formele talen worden gedefinieerd door eindige-toestandsautomaten. Er zijn twee belangrijke perspectieven van eindige-toestandsautomaten: acceptoren die kunnen zien of een string in de taal is en de tweede is de generator die alleen de strings in de taal produceert.
Deterministische eindige automaten
In deterministische automaten kunnen we, wanneer een invoer wordt gegeven, altijd bepalen in welke toestand de overgang zou zijn. Omdat dit een eindige automaat is, wordt het deterministische eindige automaten genoemd.
Grafische weergave
State Diagram is de digraphs die worden gebruikt voor grafische weergave van deterministische eindige automaten. Laten we het begrijpen met een voorbeeld. Laat deterministische eindige automaten zijn ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} en de overgangsfunctie zijn
Grafische weergave in tabelvorm
Staat diagram
Toestandsdiagram van deterministische eindige toestandsautomaten
Van het toestandsdiagram
- De staten worden vertegenwoordigd door hoekpunten.
- Overgangen worden weergegeven door de boog met een invoeralfabet.
- De lege enkele inkomende boog vertegenwoordigt de begintoestand.
- De toestand met dubbele cirkels is de eindtoestand.
Niet-deterministische eindige automaten
De automaten waarvan de outputstatus voor de gegeven input niet kan worden bepaald, worden Non-Deterministic Automata genoemd. Het wordt ook niet-deterministische eindige automaten genoemd, omdat het een eindig aantal toestanden heeft. Niet-deterministische eindige automaten worden weergegeven als de set van 5 -tuple waarbij (Q, ∑, δ, qo, F)
Q = eindige reeks staten.
= Alfabet set.
δ = de overgangsfunctie
waar 
qo = Oorspronkelijke toestand.
Grafische weergave
Niet-deterministische eindige automaten worden weergegeven met behulp van het toestandsdiagram. Laat de niet-deterministische eindige automaten
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
De overgangen zijn
Grafische weergave in tabelvorm
Staat diagram
Toestandsdiagram van niet-deterministische eindige automaten
Automaten Theorie Toepassingen
De toepassingen van automaten theorie omvatten de volgende.
- Automata-theorie is erg handig op het gebied van computertheorie, compilerproducties, AI, enz.
- Bij tekstverwerkingscompilers en hardwareontwerpen spelen eindige automaten een grote rol.
- Voor toepassingen in AI en in programmeertalen Contextvrije grammatica is erg handig.
- Op het gebied van biologie zijn cellulaire automaten nuttig.
- In theorie van eindige velden kunnen we ook de toepassing van automaten vinden.
In dit artikel hebben we een korte inleiding geleerd in de automaattheorie, talen en rekenen. Automaten bestaan al sinds de prehistorie. Met het uitvinden van nieuwe technologieën worden op dit gebied veel nieuwe ontwikkelingen gezien. Welk type automaat ben je tegengekomen?
