I dagens teknologiske æra har både hardware- og softwarefelt oplevet en enorm udvikling. Et af de vigtigste udviklingsområder blev set i metoderne til hardwaredesign. Med voksende teknologi , konceptet Hardware - Software co-design var muligt at implementere. Der udvikles forskellige metoder, som ved hjælp af software man kan fuldt ud designe og simulere hardwaresystemerne. En af sådanne metoder er Automata Theory. Automatteori er grenen af computer videnskab der beskæftiger sig med at designe den abstrakte model af computerenheder, der automatisk følger den forudbestemte rækkefølge af trin. Denne artikel diskuterer kort information om automatiseret tutorial.
Hvad er Automata Theory?
Ordet Automata stammer fra græsk, hvilket betyder 'selvvirkende'. En automaton er en matematisk model af maskinen. Automaton består af stater og overgange. Da indgangen gives til automat, foretager den en overgang til den næste tilstand afhængigt af overgangsfunktionen. Indgangene til overgangsfunktionen er nuværende status og nylige symboler. Hvis en Automaton har et begrænset antal tilstande, er det kendt som Finite Automata eller Finite State Machine . Den endelige automat er repræsenteret af en 5-tupel (Q, ∑, δ, qo, F)
Hvor,
Q = Endeligt sæt af tilstande.
∑ = endeligt sæt symboler, også kaldet automatens alfabet.
δ = overgangsfunktionen.
qo = indgangens indledende tilstand.
F = sæt af endelige tilstande af Q.
Grundlæggende terminologier for automatteori
Nogle af de grundlæggende terminologier i Automata Theory er-
1 . Alfabet : Ethvert endeligt sæt symboler i automatteori kaldes Alfabet. Repræsenteret med bogstavet∑ kaldes sættet {a, b, c, d, e,} Alfabet sæt, mens bogstaverne i sæt 'a', 'b', 'c', 'd', 'e' kaldes symboler.
to . Snor : I automata er en streng en endelig sekvens af symboler taget fra alfabetets sæt ∑, for eksempel er strengen S = ‘adeaddadc’ gyldig på alfabetet set∑ = {a, b, c, d, e,}.
3 . Strengens længde : Antallet af symboler, der findes i strengen, kaldes strengens længde. For strengen S = 'adaada' er længden af strengen | S | = 6. Hvis længden af strengen er 0, kaldes den en tom streng.
4 . Kleen Star : Det er den unære operator på symbolsættet Σ, som giver det uendelige sæt af alle mulige strenge, inklusive λ, af alle mulige længder over sættet Σ. Det repræsenteret af. For eksempel for sættet Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen lukning : Det er det uendelige sæt af alle mulige strenge i alfabetet, eksklusive λ. Det er betegnet med. For sættet Σ = {a, d}, ∑ + = {a, d, annonce, da, aa, dd,… ..}.
6 . Sprog : Sprog er delmængde af Kleene-stjernesættet * for nogle alfabet-sæt Σ. Sprog kan være endeligt eller uendeligt. For eksempel hvis et sprog tager alle de mulige strenge med længde 2 over sættet Σ = {a, d}, så er L = {aa, ad, da, dd}.
Formelle sprog og automatisk
I automatteori er formelt sprog et sæt strenge, hvor hver streng er sammensat af symboler tilhørende det endelige alfabet sæt Σ. Lad os overveje et kattesprog, der kan indeholde alle strenge fra nedenstående uendelige sæt ...
mew!
meww!
mewww !! ……
Alfabetet indstillet til kattesprog er Σ = {m, e, w,!}. Lad dette sæt bruges til en Finite State Automata Model-m. Derefter betegnes det formelle sprog præget af modellen m med
L (m)
L (m) = {'mew!', 'Meww!', 'Mewww', ……}
Automaton er nyttigt til at definere et sprog, fordi det kan udtrykke et uendeligt sæt i en lukket form. Formelle sprog er ikke de samme som de naturlige sprog, vi taler i vores daglige liv. Et formelt sprog kan betegne maskinens forskellige tilstande i modsætning til vores almindelige sprog. Formelt sprog bruges til at modellere en del af det naturlige sprog som f.eks. Syntaks osv ... Formelle sprog defineres ved endelig tilstandsautomat. Der er to hovedperspektiver for Finite state automata- Acceptorer, der kan fortælle, om en streng er på sproget, og den anden er generatoren, der kun producerer strengene på sproget.
Deterministisk Finite Automata
I deterministisk type automatik, når et input gives, kan vi altid bestemme, i hvilken tilstand overgangen ville være. Da dette er en endelig automat, kaldes den Deterministic Finite Automata.
Grafisk repræsentation
Tilstandsdiagram er de grafer, der bruges til grafisk repræsentation af Deterministic Finite Automata. Lad os forstå med et eksempel. Lad deterministiske endelige automater være ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} og overgangsfunktionen være
Grafisk repræsentation i tabelform
Stat Diagram
Tilstandsdiagram for deterministisk endelig tilstandsautomat
Fra tilstandsdiagrammet
- Staterne er repræsenteret ved hjørner.
- Overgange er repræsenteret af buen mærket med et inputalfabet.
- Den tomme enkelt indkommende lysbue repræsenterer den oprindelige tilstand.
- Staten med dobbelte cirkler er den endelige tilstand.
Ikke-deterministisk endelig automat
Automaten, hvor outputtilstanden for den givne input ikke kan bestemmes, kaldes ikke-deterministisk automata. Det kaldes også Non-Deterministic Finite Automata, da det har et endeligt antal stater. Ikke-deterministisk Finite Automata er repræsenteret som sættet med 5 –tuple hvor (Q, ∑, δ, qo, F)
Q = endeligt sæt stater.
∑ = Alfabet sæt.
δ = overgangsfunktionen
hvor : 
qo = Oprindelig tilstand.
Grafisk repræsentation
Ikke-deterministiske endelige automater er repræsenteret ved hjælp af tilstandsdiagrammet. Lad den ikke-deterministiske endelige automatik være
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Overgangene er
Grafisk repræsentation i tabelform
Stat Diagram
Tilstandsdiagram over ikke-deterministisk endelig automat
Automata Theory Applications
Anvendelserne af automatteori inkluderer følgende.
- Automatalteori er meget nyttig inden for teori om beregning, compiler-produktioner, AI osv.
- For tekstbehandlingscompilere og hardwaredesign spiller finite automata en vigtig rolle.
- Til applikationer i AI og in programmeringssprog , Kontekstfri grammatik er meget nyttig.
- Inden for biologi er cellulære automater nyttige.
- I teorien om begrænsede felter kan vi også finde anvendelsen af Automata.
I denne artikel har vi lært en kort introduktion til automatteoriens sprog og beregning. Automater har eksisteret siden den forhistoriske periode. Med opfindelsen af nye teknologier ses mange nye udviklinger inden for dette felt. Hvilken type automat er du stødt på?
