Sa panahong teknolohikal ngayon ang parehong hardware at larangan ng software ay nakakita ng napakalaking kaunlaran. Ang isa sa mga pangunahing larangan ng pag-unlad ay nakita sa mga pamamaraan ng mga disenyo ng Hardware. Kasama ang lumalagong teknolohiya , ang konsepto ng Hardware - Ang software co-design ay posible na ipatupad. Iba't ibang mga pamamaraan ay binuo sa pamamagitan ng kung saan, gumagamit ng software ang isa ay maaaring ganap na magdisenyo at gayahin ang mga sistema ng hardware. Ang isa sa mga ganitong pamamaraan ay ang Teoryang Automata. Ang teoryang Automata ay ang sangay ng computer science na pakikitungo sa pagdidisenyo ng abstract na modelo ng mga aparato sa computing na awtomatikong sumusunod sa tinukoy na pagkakasunud-sunod ng mga hakbang. Tinalakay ng artikulong ito ang maikling impormasyon sa tutorial ng automata.
Ano ang Teorya ng Automata?
Ang salitang Automata ay nagmula sa Greek, na nangangahulugang 'self-acting'. Ang isang Automaton ay isang modelo ng matematika ng makina. Ang automaton ay binubuo ng mga estado at pagbabago. Tulad ng input na ibinigay sa automaton gumagawa ito ng paglipat sa susunod na estado, depende sa pagpapaandar ng paglipat. Ang mga input sa pagpapaandar ng paglipat ay kasalukuyang estado at mga kamakailang simbolo. Kung ang isang Automaton ay may isang may hangganan na bilang ng mga estado, ito ay kilala bilang Finite Automata o Makina ng Estado ng Estado . Ang may hangganang automata ay kinakatawan ng isang 5-tuple (Q, ∑, δ, qo, F)
Kung saan,
Q = May wakas na hanay ng mga estado.
∑ = may hangganan na hanay ng mga simbolo na tinatawag ding Alpabeto ng automata.
δ = ang paglipat ng function.
qo = paunang estado ng input.
F = hanay ng mga huling estado ng Q.
Pangunahing Mga Terminolohiya ng Teoryang Automata
Ang ilan sa mga pangunahing terminolohiya ng Automata Theory ay-
1 . Alpabeto : Ang anumang may hangganang hanay ng mga simbolo sa teorya ng automata ay kilala bilang Alphabet. Kinakatawan ng letrang∑ ang hanay na {a, b, c, d, e,} ay tinawag na hanay ng alpabeto, samantalang ang mga titik ng hanay na 'a', 'b', 'c', 'd', 'e' ay tinatawag na simbolo.
dalawa . String : Sa automata, ang isang string ay isang may hangganang pagkakasunud-sunod ng mga simbolo na kinuha mula sa hanay ng alpabeto ∑, Halimbawa, ang string S = ‘adeaddadc’ ay may bisa sa hanay ng alpabeto∑ = {a, b, c, d, e,}.
3 . Haba ng String : Ang bilang ng mga simbolo na naroroon sa string ay kilala bilang Haba ng string. Para sa string na S = ‘adaada’ haba ng string ay | S | = 6. Kung ang haba ng string ay 0, pagkatapos ito ay tinatawag na isang walang laman na string.
4 . Kleen Star : Ito ang unary operator sa hanay ng mga simbolo Σ, na nagbibigay ng walang katapusang hanay ng lahat ng mga posibleng string, kabilang ang λ, ng lahat ng posibleng haba sa itinakdang Σ. Kinatawan ito ni. Halimbawa, para sa itinakdang Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen Closure : Ito ang walang katapusang hanay ng lahat ng mga posibleng mga string ng hanay ng alpabeto na hindi kasama ang λ. Ito ay sinasabihan ng. Para sa itinakdang Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 . Wika : Ang wika ay ang subset ng Kleene star set∑ * para sa ilang hanay ng Alpabeto Σ. Ang wika ay maaaring may hangganan o walang hanggan. Halimbawa kung ang isang wika ay tumatagal ng lahat ng mga posibleng tali ng haba 2 sa itinakdang Σ = {a, d}, pagkatapos ay L = {aa, ad, da, dd}.
Pormal na Mga Wika at Automata
Sa teorya ng automata, ang Pormal na wika ay isang hanay ng mga string, kung saan naroon ang bawat string binubuo ng mga simbolo na kabilang sa may hangganan na hanay ng Alpabeto Σ. Isaalang-alang natin ang isang wika ng pusa, na maaaring maglaman ng anumang mga string mula sa ibaba na walang katapusang hanay ...
mew!
meww!
akowww !! ……
Ang itinakdang alpabeto para sa wika ng pusa ay Σ = {m, e, w,!}. Hayaan ang set na ito na magamit para sa isang Finite State Automata Model-m. Pagkatapos ang pormal na wikang nailalarawan sa pamamagitan ng modelo m ay tinukoy ng
L (m)
L (m) = {'mew!', 'Meww!', 'Mewww', ……}
Ang automaton ay kapaki-pakinabang para sa pagtukoy ng isang wika dahil maaari itong ipahayag ang isang walang katapusang hanay sa isang saradong form. Ang mga pormal na wika ay hindi katulad ng mga natural na wika na sinasalita natin sa ating pang-araw-araw na buhay. Ang isang pormal na wika ay maaaring magpahiwatig ng iba't ibang mga estado ng makina, hindi katulad ng aming mga regular na wika. Ginagamit ang pormal na wika upang i-modelo ang isang bahagi ng natural na wika tulad ng syntax atbp ... Ang mga pormal na wika ay tinukoy ng may hangganang estado ng automata. Mayroong dalawang pangunahing pananaw ng Finite state automata- Ang mga tatanggap na maaaring sabihin kung ang isang string ay nasa wika at ang pangalawa ay ang generator na gumagawa lamang ng mga string sa wika.
Deterministic Finite Automata
Sa Deterministic na uri ng automata, kapag ibinigay ang isang input, palagi nating matutukoy kung aling estado ang magiging paglipat. Dahil ito ay isang may hangganang automaton, tinawag itong Deterministic Finite Automata.
Grapikal na presentasyon
Ang State Diagram ay ang mga digraph na ginamit para sa grapikong representasyon ng Deterministic Finite Automata. Unawain natin sa isang halimbawa. Hayaan ang deterministic finite automata na…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} at ang function ng paglipat ay
Form ng Talaan ng Tabular na graphic
Diagram ng Estado
Diagram ng Estado ng Deterministic Finite State Automata
Mula sa diagram ng estado
- Ang mga estado ay kinakatawan ng mga vertex.
- Ang mga transisyon ay kinakatawan ng arc na may label na isang input alpabeto.
- Ang walang laman na solong papasok na arko ay kumakatawan sa paunang estado.
- Ang estado na may dobleng bilog ay ang pangwakas na estado.
Non Deterministic Finite Automata
Ang automata kung saan ang estado ng output para sa ibinigay na input ay hindi matukoy ay tinatawag na Non-Deterministic Automata. Tinatawag din itong Non-Deterministic Finite Automata, dahil mayroon itong may hangganan na bilang ng mga estado. Ang non-deterministic na Finite Automata ay kinakatawan bilang hanay ng 5 –puple kung saan (Q, ∑, δ, qo, F)
Q = may hangganan na hanay ng mga estado.
= Itinakda ang alpabeto.
= ang paglipat function
kung saan : 
qo = Paunang estado.
Grapikal na presentasyon
Ang non-deterministic finite automata ay kinakatawan sa tulong ng diagram ng estado. Hayaan ang Non-Deterministic Finite Automata na-
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Ang mga pagbabago ay
Form ng Talaan ng Tabular na graphic
Diagram ng Estado
Diagram ng Estado ng Non-Deterministic Finite Automata
Mga Application ng Teoryang Automata
Ang mga aplikasyon ng teorya ng automata isama ang sumusunod.
- Ang teorya ng automata ay lubhang kapaki-pakinabang sa mga larangan ng Teorya ng pagkalkula, mga produksyon ng compiler, AI, atbp.
- Para sa mga tagataguyod ng pagpoproseso ng teksto at mga disenyo ng hardware, ang may limitasyong automata ay may pangunahing papel.
- Para sa mga aplikasyon sa AI at sa mga wika sa programa , Napaka kapaki-pakinabang ng gramatika na walang konteksto.
- Sa larangan ng biology, kapaki-pakinabang ang cellular automata.
- Sa teorya ng may hangganang mga patlang din maaari naming makita ang aplikasyon ng Automata.
Sa artikulong ito, natutunan namin ang isang maikling pagpapakilala sa mga wika ng automata na teorya at pagkalkula. Ang Automata ay nasa paligid mula pa noong panahon ng sinaunang panahon. Sa pag-imbento ng mga bagong teknolohiya maraming mga bagong pagpapaunlad ang nakikita sa larangang ito. Aling uri ng automata ang nakatagpo mo?
