I dagens tekniska era har både hårdvaru- och mjukvarufält utvecklats enormt. Ett av de viktigaste utvecklingsområdena sågs i metoderna för hårdvarudesign. Med växande teknik , begreppet maskinvara - programvara samdesign var möjligt att implementera. Olika metoder utvecklas genom vilka, med programvara man kan helt utforma och simulera hårdvarusystemen. En av sådana metoder är Automata Theory. Automatateori är en gren av datavetenskap som handlar om att designa den abstrakta modellen av datoranordningar som automatiskt följer den förutbestämda sekvensen av steg. Den här artikeln diskuterar kort information om handledning om automat.
Vad är Automata Theory?
Ordet Automata kommer från grekiska, vilket betyder ”självverkande”. En automat är en matematisk modell av maskinen. Automaton består av tillstånd och övergångar. Eftersom ingången ges till automat gör den en övergång till nästa tillstånd, beroende på övergångsfunktionen. Ingångarna till övergångsfunktionen är nuvarande tillstånd och senaste symboler. Om en Automaton har ett begränsat antal tillstånd kallas det Endlig Automata eller Finite State Machine . De ändliga automaterna representeras av en 5-tupel (Q, ∑, δ, qo, F)
Var,
Q = Slutlig uppsättning tillstånd.
∑ = ändlig uppsättning symboler som också kallas automatens alfabet.
δ = övergångsfunktionen.
qo = ingångens initiala tillstånd.
F = uppsättning av slutliga tillstånd för Q.
Grundläggande terminologier för automatteori
Några av de grundläggande terminologierna i Automata Theory är-
1 . Alfabet : Varje begränsad uppsättning symboler i automatteorin kallas alfabetet. Representeras av bokstaven∑ uppsättningen {a, b, c, d, e,} kallas alfabetuppsättning, medan bokstäverna i uppsättning 'a', 'b', 'c', 'd', 'e' kallas symboler.
två . Sträng : I automata är en sträng en ändlig sekvens av symboler hämtade från alfabetuppsättningen ∑. Till exempel är strängen S = ‘adeaddadc’ giltig på alfabetuppsättningen∑ = {a, b, c, d, e,}.
3 . Strängens längd : Antalet symboler som finns i strängen kallas strängens längd. För strängen S = 'adaada' är strängens längd | S | = 6. Om strängens längd är 0 kallas den en tom sträng.
4 . Kleen Star : Det är den unara operatören på uppsättningen symboler Σ, som ger den oändliga uppsättningen av alla möjliga strängar, inklusive λ, av alla möjliga längder över uppsättningen Σ. Det representeras av. Till exempel för uppsättningen Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen stängning : Det är den oändliga uppsättningen av alla möjliga strängar i alfabetet, exklusive λ. Det betecknas med. För uppsättningen Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . Språk : Språk är delmängden av Kleene-stjärnuppsättningen * * för vissa alfabetuppsättningar Σ. Språket kan vara ändligt eller oändligt. Till exempel om ett språk tar alla möjliga strängar av längd 2 över uppsättningen Σ = {a, d}, då L = {aa, ad, da, dd}.
Formella språk och automatik
I automatteori är formellt språk en uppsättning strängar där varje sträng är består av symboler tillhör det ändliga alfabetet set. Låt oss överväga ett katt språk, som kan innehålla alla strängar från nedan oändliga uppsättningar ...
mew!
meww!
mewww !! ……
Alfabetet för kattens språk är Σ = {m, e, w,!}. Låt denna uppsättning användas för en Finite State Automata Model-m. Sedan betecknas det formella språket som kännetecknas av modellen m med
L (m)
L (m) = {'mew!', 'Meww!', 'Mewww', ……}
Automaton är användbart för att definiera ett språk eftersom det kan uttrycka en oändlig uppsättning i stängd form. Formella språk är inte samma som de naturliga språken vi talar i vårt dagliga liv. Ett formellt språk kan beteckna maskinens olika tillstånd, till skillnad från våra vanliga språk. Formellt språk används för att modellera en del av det naturliga språket, såsom syntax etc ... Formella språk definieras av slutliga tillståndsautomater. Det finns två huvudperspektiv på Finite state automata- Acceptorer som kan avgöra om en sträng finns i språket och den andra är generatorn som bara producerar strängarna i språket.
Deterministic Finite Automata
I deterministisk typ av automat, när en ingång ges, kan vi alltid avgöra till vilket tillstånd övergången skulle vara. Eftersom detta är en ändlig automat kallas den Deterministic Finite Automata.
Grafisk representation
State Diagram är de grafer som används för grafisk representation av Deterministic Finite Automata. Låt oss förstå med ett exempel. Låt deterministiska ändliga automater vara ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} och övergångsfunktionen vara
Grafisk representation Tabellform
Statligt diagram
Statligt diagram över deterministiska ändliga tillståndsautomater
Från tillståndsdiagrammet
- Staterna representeras av hörnpunkter.
- Övergångar representeras av bågen märkt med ett inmatningsalfabet.
- Den tomma enstaka inkommande bågen representerar det initiala tillståndet.
- Staten med dubbla cirklar är det slutliga tillståndet.
Icke bestämd slutlig automat
Automaten där utmatningstillståndet för den angivna ingången inte kan bestämmas kallas icke-deterministisk automata. Det kallas också Non-Deterministic Finite Automata, eftersom det har ett begränsat antal stater. Icke-deterministisk Finite Automata representeras som uppsättningen 5 –tuple där (Q, ∑, δ, qo, F)
Q = begränsad uppsättning stater.
∑ = Alfabetuppsättning.
5 = övergångsfunktionen
var : 
qo = Initialtillstånd.
Grafisk representation
Icke-deterministiska ändliga automater representeras med hjälp av tillståndsdiagrammet. Låt den icke-deterministiska ändliga automaten bli
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Övergångarna är
Grafisk representation Tabellform
Statligt diagram
Statligt diagram över icke-deterministisk ändlig automat
Automata Theory Applications
Tillämpningarna av automatteori inkluderar följande.
- Automatteori är mycket användbar inom områdena beräkningsteori, kompilatorproduktion, AI, etc.
- För kompilatorer för textbearbetning och hårdvarudesign spelar ändliga automater en viktig roll.
- För applikationer inom AI och in programmeringsspråk , Kontextfri grammatik är mycket användbar.
- Inom biologin är cellulära automator användbara.
- I teorin om begränsade fält kan vi också hitta tillämpningen av Automata.
I den här artikeln har vi lärt oss en kort introduktion till automatteorinspråk och beräkning. Automatar har funnits sedan förhistorisk period. Med uppfinningen av ny teknik ses många nya utvecklingar inom detta område. Vilken typ av automat har du stött på?
