I dagens teknologiske tid har både maskinvare- og programvarefelt hatt en enorm utvikling. Et av de viktigste utviklingsområdene ble sett i metodene for maskinvaredesign. Med voksende teknologi , var konseptet med maskinvare - programvaresamdesign mulig å implementere. Ulike metoder er utviklet som, ved hjelp av programvare man kan utforme og simulere maskinvaresystemene fullt ut. En av slike metoder er Automata Theory. Automatteori er grenen til informatikk som handler om å designe den abstrakte modellen for databehandlingsenheter som automatisk følger den forhåndsbestemte trinnsekvensen. Denne artikkelen diskuterer kort informasjon om automatisering.
Hva er Automata Theory?
Ordet Automata er avledet fra gresk, som betyr 'selvvirkende'. En automaton er en matematisk modell av maskinen. Automaton består av tilstander og overganger. Når inngangen er gitt til automat, gjør den en overgang til neste tilstand, avhengig av overgangsfunksjonen. Inngangene til overgangsfunksjonen er nåværende tilstand og nylige symboler. Hvis en automaton har et endelig antall stater, er det kjent som Finite Automata eller Finite State Machine . De endelige automatene er representert med en 5-tupel (Q, ∑, δ, qo, F)
Hvor,
Q = Endelig sett med tilstander.
∑ = endelig sett med symboler også kalt Alfabetet for automaten.
δ = overgangsfunksjonen.
qo = inngangens innledende tilstand.
F = sett med endelige tilstander til Q.
Grunnleggende terminologier for Automata Theory
Noen av de grunnleggende terminologiene i Automata Theory er-
1 . Alfabet : Ethvert endelig sett med symboler i automatteorien er kjent som Alfabetet. Representert av bokstaven∑ settet {a, b, c, d, e,} kalles alfabet sett, mens bokstavene i settet 'a', 'b', 'c', 'd', 'e' kalles symboler.
to . String : I automata er en streng en endelig sekvens av symboler hentet fra alfabet settet ∑. For eksempel er strengen S = ‘adeaddadc’ gyldig på alfabetet sett∑ = {a, b, c, d, e,}.
3 . Lengde på streng : Antall symboler som er tilstede i strengen er kjent som Lengde på streng. For strengen S = ‘adaada’ er lengden på strengen | S | = 6. Hvis lengden på strengen er 0, kalles den en tom streng.
4 . Kleen Star : Det er den unare operatoren på symbolsettet Σ, som gir det uendelige settet med alle mulige strenger, inkludert λ, av alle mulige lengder over settet Σ. Det representeres av. For eksempel for settet Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen nedleggelse : Det er det uendelige settet med alle mulige strenger i alfabetet, unntatt λ. Det er betegnet med. For settet Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . Språk : Språk er delsett av Kleene-stjernesettet∑ * for noen Alfabet-sett Σ. Språk kan være endelig eller uendelig. For eksempel hvis et språk tar alle mulige strenger med lengde 2 over settet Σ = {a, d}, så L = {aa, ad, da, dd}.
Formelle språk og automata
I automatteori er formelt språk et sett med strenger der hver streng er sammensatt av symboler tilhører det endelige alfabet settet Σ. La oss vurdere et kattespråk, som kan inneholde strenger fra det uendelige settet nedenfor ...
mew!
meww!
mewww !! ……
Alfabetet som er satt for kattespråk er Σ = {m, e, w,!}. La dette settet brukes til en Finite State Automata Model-m. Deretter betegnes det formelle språket preget av modellen m med
L (m)
L (m) = {‘mew!’, ‘Meww!’, ‘Mewww ', ……}
Automaton er nyttig for å definere et språk fordi det kan uttrykke et uendelig sett i lukket form. Formalspråk er ikke det samme som de naturlige språkene vi snakker i vårt daglige liv. Et formelt språk kan betegne maskinens forskjellige tilstander, i motsetning til våre vanlige språk. Formelt språk brukes til å modellere en del av det naturlige språket, for eksempel syntaks osv ... Formalspråk er definert av endelige tilstandsautomater. Det er to hovedperspektiver av Finite state automata- Akseptorer som kan fortelle om en streng er i språket, og den andre er generatoren som bare produserer strengene i språket.
Deterministic Endite Automata
I deterministisk type automatikk, når en inngang er gitt, kan vi alltid bestemme hvilken tilstand overgangen vil være. Siden dette er en endelig automat, kalles den Deterministic Finite Automata.
Grafisk representasjon
Tilstandsdiagram er digrafene som brukes for grafisk fremstilling av Deterministic Finite Automata. La oss forstå det med et eksempel. La deterministiske endelige automater være ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} og overgangsfunksjonen være
Grafisk fremstilling Tabellform
Statlig diagram
Tilstandsdiagram over deterministisk endelig tilstandsautomat
Fra tilstandsdiagrammet
- Statene er representert med hjørner.
- Overganger er representert med buen merket med et inngangsalfabet.
- Den tomme enkeltinnkommende buen representerer den opprinnelige tilstanden.
- Staten med doble sirkler er den endelige tilstanden.
Ikke deterministisk endelig automat
Automaten der utgangstilstanden for den gitte inngangen ikke kan bestemmes, kalles ikke-deterministisk automata. Det kalles også Non-Deterministic Finite Automata, da det har et endelig antall stater. Ikke-deterministisk Finite Automata er representert som settet med 5 –tuple hvor (Q, ∑, δ, qo, F)
Q = endelig sett med stater.
∑ = Alfabet sett.
δ = overgangsfunksjonen
hvor : 
qo = Opprinnelige tilstand.
Grafisk representasjon
Ikke-deterministiske endelige automater er representert ved hjelp av tilstandsdiagrammet. La den ikke-deterministiske endelige automaten være
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Overgangene er
Grafisk fremstilling Tabellform
Statlig diagram
Tilstandsdiagram over ikke-deterministisk endelig automat
Automata Theory Applications
Søknadene til automatteori Inkluder følgende.
- Automata-teorien er veldig nyttig innen teori for beregning, kompilatorproduksjoner, AI, etc.
- For tekstbehandlings kompilatorer og maskinvaredesign spiller endelige automata en stor rolle.
- For applikasjoner i AI og i programmerings språk , Kontekstfri grammatikk er veldig nyttig.
- Innen biologi er Cellular automata nyttige.
- I teorien om begrensede felt kan vi også finne applikasjonen til Automata.
I denne artikkelen har vi lært en kort introduksjon til automatteoriens språk og beregning. Automata har eksistert siden forhistorien. Med oppfinnelsen av ny teknologi blir mange nye utviklinger sett i dette feltet. Hvilken type automat har du kommet over med?
