vaiko samprata 

Pagrindinės automatų teorijos sąvokos. Automatų teorija Abstrakčių automatų teorijos problemų grupės

automatų teorija
Automatų teorija- diskrečiosios matematikos skyrius, nagrinėjantis abstrakčius automatus - kompiuterius, pateiktus matematinių modelių pavidalu - ir užduotis, kurias jie gali išspręsti.

Automatų teorija glaudžiausiai susijusi su algoritmų teorija: automatas paverčia diskrečią informaciją žingsneliais į atskirus laiko momentus, o rezultatą generuoja tam tikro algoritmo žingsneliais.

  • 1 Terminija
  • 2 Taikymas
    • 2.1 Tipinės užduotys
  • 3 Taip pat žr
  • 4 Literatūra
  • 5 Nuorodos

Terminija

Simbolis- bet koks atominis duomenų blokas, galintis turėti įtakos mašinai. Dažniausiai simbolis yra raidė bendrine kalba, tačiau tai gali būti, pavyzdžiui, grafinis diagramos elementas.

  • Žodis- simbolių eilutė, sukurta sujungimo (sujungimo) būdu.
  • Abėcėlė- baigtinis skirtingų simbolių rinkinys (daug simbolių)
  • Kalba- žodžių rinkinys, sudarytas iš nurodytos abėcėlės simbolių. Gali būti baigtinis arba begalinis.


Automatas

Automatai gali būti deterministiniai arba nedeterministiniai.

Deterministinis baigtinis automatas (DFA)
  • yra tokia perėjimo funkcija
  • - pradinė būsena
Nedeterministinis baigtinis automatas (NFA)- penkių elementų seka (kortelė), kur:
  • - automato būsenų rinkinys
  • - kalbos, kurią supranta automatas, abėcėlė
  • yra pereinamasis santykis, kur yra tuščias žodis. Tai yra, NFA gali pereiti iš būsenos q į būseną p, skirtingai nei DFA, per tuščią žodį, taip pat pereiti iš q į kelias būsenas (kas vėlgi neįmanoma DFA).
  • - pradinių būsenų rinkinys
  • - galutinių būsenų rinkinys.
Žodis automatas skaito baigtinę simbolių eilutę a1,a2,…., an , kur ai ∈ Σ, kuri vadinama įvesties žodžiu.Visų žodžių aibė rašoma kaip Σ*. Gautas žodis Žodį w ∈ Σ* priima automatas, jei qn ∈ F.

Laikoma, kad kalba L skaitoma (priimama) automato M, jei ji susideda iš žodžių w pagal abėcėlę taip, kad jei šie žodžiai įvedami į M, apdorojimo pabaigoje ji patenka į vieną iš priimančių būsenų F:

Paprastai automatas pereina iš būsenos į būseną naudodamas perėjimo funkciją, skaitydamas vieną simbolį iš įvesties. Yra automatų, kurie gali pereiti į naują būseną neskaitydami simbolio. Perėjimo funkcija neskaitant simbolio vadinama -jump (epsilon-jump).

Taikymas

Automatų teorija yra visų skaitmeninių technologijų ir programinė įranga, taigi, pavyzdžiui, kompiuteris yra ypatingas baigtinių būsenų mašinos praktinio įgyvendinimo atvejis.

Dalis automatų teorijos matematinio aparato yra tiesiogiai naudojama kuriant formaliųjų kalbų, įskaitant programavimo kalbas, lekserius ir analizatorius, taip pat kuriant kompiliatorius ir kuriant pačias programavimo kalbas.

Kitas svarbus automatų teorijos pritaikymas yra matematiškai griežtas problemų sprendžiamumo ir sudėtingumo nustatymas.

Tipiškos užduotys

  • Automatų konstravimas ir minimizavimas- abstraktaus automato sukūrimas iš tam tikros klasės, kuris išsprendžia duotą problemą (priima tam tikrą kalbą), galbūt vėliau sumažinant būsenų skaičių arba perėjimų skaičių.
  • Automatų sintezė- duotų „elementarių automatų“, lygiaverčių tam tikram automatui, sistemos sukūrimas. Toks automatas vadinamas struktūriniu. Jis naudojamas, pavyzdžiui, skaitmeninio sintezėje elektros grandinės ant tam tikro elemento pagrindo.

taip pat žr

  • Siurblys Lemma
  • Abstraktus automatas
  • Žaidimas "Gyvenimas"
  • Minimali automato forma
  • Šenono-Lupanovo teorema

Literatūra

  • Johnas Hopcroftas, Rajeevas Motwani, Jeffrey Ullmanas. Įvadas į automatų teoriją, kalbas ir skaičiavimą. - M.: Williams, 2002. - S. 528. - ISBN 0-201-44124-1.
  • Kasjanovas V. N. Paskaitos apie formaliųjų kalbų teoriją, automatus ir skaičiavimo sudėtingumą. - Novosibirskas: NSU, 1995. - C. 112.

Nuorodos

  • Automatų teorijos taikymas

automatų teorija

Federalinė švietimo agentūra

valstybė švietimo įstaiga aukštasis profesinis išsilavinimas

„MASKVOS VALSTYBINIO UNIVERSITETAS

INSTRUMENTAI IR INFORMATIKA »

IT-4 katedra „Asmeniniai kompiuteriai ir tinklai“

"PATVIRTINTI"

Skyriaus vedėjas IT-4

Michailovas B.M.

„___“ __________________ 2007 m

PASKAITOS

1425 disciplinoje „Automatų teorija“

IT fakulteto II kurso studentams

Specialybės 230101

„Kompiuteriai, kompleksai, sistemos ir tinklai“

Aptartas skyriaus posėdyje

„___“ ________________ 2007 m

_____ protokolas Nr.

Maskva 2007 m

^ Bendrosios nuostatos

Disciplinos tikslai ir uždaviniai

Disciplinos tikslas – pristatyti programinės ir techninės įrangos organizavimo asmeniniuose kompiuteriuose principus naudojant automatų teoriją, įsisavinant kompiuterių programinės ir techninės įrangos kūrimo įgūdžius.

^ Reikalavimai disciplinos turinio įsisavinimo lygiui

Žinios, įgytos įsisavinant discipliną:


  • Automatų teorijos principai ir pagrindinės sąvokos;

  • Automatų teorijos taikymas konstruojant algoritminių kalbų vertėjus;

  • Automatų teorijos taikymas kuriant įrenginius ir atskirą įrangą asmeniniuose kompiuteriuose;
Įgūdžiai ir įgūdžiai, įgyti įsisavinant discipliną:

  • Automatų teorijos taikymas taikomiesiems uždaviniams spręsti;

  • Atskirų įrenginių projektavimas;

  • Vertėjo dizainas;

Pagrindinė literatūra

1. Saveliev A.Ya. Informatikos pagrindai: vadovėlis universitetams.-M.: Leidykla MSTU im. N. Bauman, 2001.-328s.

2. Karpovas Yu.G.

3. Zaicevas E.I. Automatų teorija: Vadovėlis.-M.: MGAPI, 2002.-59s.

papildomos literatūros

1. Hopcroft D., Motwani R., Įvadas į automatų teoriją, kalbas ir skaičiavimus: vertimas iš anglų kalbos-M.: Izdat. Domas Viljamsas, 2002.-528psl.

Paskaita numeris 1.

Pagrindinės sąvokos ir apibrėžimai

Trukmė: 2 valandos (90) minučių

1.1. Pagrindinės (pagrindinės) problemos (akimirkos)

„Automatų teorijos“ disciplinos vieta daugelyje katedroje skaitytų disciplinų

Automatų teorijos objektai

Automatų teorijos problemos

Pagrindinės sąvokos ir apibrėžimai.

^ AUTOMATŲ TEORIJA.

1.2.1. Automatų teorijos pagrindai. Iki 20 minučių

Mašina (iš graikų   - veikiantis savarankiškai) - valdymo sistema, kuris yra baigtinių būsenų mašina arba tam tikra jo modifikacija, gauta pakeitus jo komponentus ar veikimą. Pagrindinė sąvoka – baigtinis automatas – atsirado XX amžiaus viduryje dėl bandymų matematine kalba apibūdinti nervų sistemų funkcionavimą, universalius kompiuterius ir kt. tikros mašinos. būdingas bruožas toks aprašymas yra diskretiškumas atitinkamus matematinius modelius ir jų parametrų diapazonų baigtinumą, dėl ko susidaro baigtinio automato samprata.

Automatų teorija yra teorijos skyrius valdymo sistemos studijuojant matematiniai modeliai diskretieji informacijos keitikliai, vadinami kulkosvaidis. Tam tikru požiūriu tokie keitikliai yra ir realūs įrenginiai (kompiuteriai, automatai, gyvi organizmai ir kt.), ir abstrakčios sistemos (pavyzdžiui, formali sistema, aksiomatinės teorijos ir kt.). Labiausiai susiję su algoritmų teorija.

Dauguma automatų teorijos problemų yra bendros pagrindiniams valdymo sistemų tipams. Tai automatų analizės ir sintezės problemos, užbaigtumo, minimizavimo, lygiaverčių automatų transformacijų problemos ir kt. Analizės užduotis susideda iš jo elgesio apibūdinimo remiantis tam tikru automatu arba, remiantis nepilnais duomenimis apie automatą ir jo veikimą, vienokių ar kitokių jo savybių nustatymo. Sintezės užduotis automatas susideda iš automato su iš anksto nustatyto elgesio ar veikimo sukūrimas. Išsamumo iššūkis yra išsiaiškinti, ar rinkinys turi M"M automatai su užbaigtumo savybe, t.y. ar sutampa su M visų automatų rinkinys, gautas baigtiniu skaičiumi kai kurių operacijų taikymų automatams iš tam tikro automatų poaibio M" . Lygiaverčių transformacijų problema bendras vaizdas yra rasti transformacijos taisyklių sistemą (vadinamą pilna sistema taisyklės) automatai, kurie tenkina tam tikras sąlygas ir leidžia savavališką automatą paversti bet kuriuo lygiaverčiu automatu (du automatai yra lygiaverčiai, jei jų elgsena yra tokia pati. Automato elgsena yra matematinė sąvoka, apibūdinanti automato sąveiką su išorine aplinka. Pavyzdys išorinė aplinka baigtinis automatas yra įvesties žodžių rinkinys, o elgsena yra žodyno funkcija, kurią įgyvendina automatas, arba automato atstovaujamas įvykis.)

Be aukščiau išvardytų, automatų teorijoje yra specifines problemas būdingas automatams. Taigi, atsižvelgiant į problemos sąlygas, patogu įjungti automato elgesį skirtingomis kalbomis, dėl kurių svarbios užduotys yra pakankamai patogios adekvačios kalbos pasirinkimas ir vertimas iš vienos kalbos į kitą. Glaudžiai susijęs su sintezės ir lygiaverčių transformacijų problemomis minimizavimo problema automato būsenų skaičių, taip pat atitinkamų įverčių gavimą. Glaudus klausimų ratas kyla dėl vienos klasės automatų elgesio modeliavimo kitos klasės automatais. Čia taip pat domina modeliavimo automatų sumažinimo ir jų sudėtingumo įvertinimo klausimai. Ypatinga automatų teorijos šaka yra susijusi su vadinami eksperimentais su automatais(t.y. informacijos apie automatų vidinę sandarą gavimo būdai pagal jų elgesį). Pagrindinė užduotis čia yra gauti tam tikrą informaciją apie automato sandarą, stebint jo reakciją į tam tikrus išorinius poveikius. Tai sukelia didelis ratas problemos, susijusios su eksperimentų klasifikavimu ir problemų išsprendžiamumo tam tikro tipo eksperimentais klausimais, taip pat su minimalių eksperimentų trukmės įverčiais, kurių pakanka tam tikroms problemoms išspręsti. Eksperimento su automatais sąvoka taip pat naudojama uždaviniuose patikimumas ir kontrolė valdymo sistemos, ypač automatų valdymas. Daugelis aukščiau išvardytų problemų gali būti vertinamos kaip algoritminės problemos. Dėl baigtinių automatų dauguma jų turi teigiamą sprendimą.

Automatų teorija pritaikoma tiek kitose matematikos srityse, tiek sprendžiant praktines problemas. Pavyzdžiui, kai kurių formalių skaičiavimų išsprendžiamumas įrodomas automatų teorijos pagalba. Automatų teorijos metodų ir sąvokų taikymas formaliųjų ir natūralių kalbų studijoms paskatino matematinės lingvistikos atsiradimą (matematinė lingvistika yra matematinė disciplina, kurios dalykas yra formalaus aparato, skirto natūralių ir natūralių kalbų struktūrai apibūdinti, sukūrimas). kai kurios dirbtinės kalbos.) Automato sąvoka gali pasitarnauti kaip pavyzdinis objektas sprendžiant įvairiausias problemas , o tai leidžia panaudoti automatų teoriją įvairiuose moksliniuose ir taikomuosiuose tyrimuose.

^ 1.2.2. Automatų teorija sprendžiami uždaviniai ir uždaviniai. Iki 30 minučių

Automatų teorija- diskrečiosios matematikos skyrius, tiriantis realių (techninių, biologinių, ekonominių) ar galimų įrenginių, apdorojančių diskrečią informaciją diskrečiaisiais laiko žingsniais, matematinius modelius.

Šioje teorijoje jos kryptys yra gana aiškiai nustatytos dėl:


  1. tiriamų automatų tipų parinkimas (baigtinis, begalinis, deterministinis, tikimybinis, autonominis, kombinacinis, be išvesties)

  2. priimtas abstrakcijos lygis (abstrakčiai ir struktūriniai automatai)

  3. taikomosios matematikos specifika (algebrinė automatų teorija)
Tuo pačiu metu nagrinėjamų objektų diskrečiuose modeliuose atsižvelgiama tik į vykstančių automato pokyčių procesų logiką, neatsižvelgiant į kiekybines charakteristikas.

Centrinės skaitomos teorijos problemos yra sintaksės ir analizės problemos (t.y. automato funkcinės schemos sukūrimas pagal duotą elgseną ir automato elgesio aprašymas pagal žinomą struktūrą). Šios problemos yra glaudžiai susijusios su pilnumo, lygiavertiškumo ir automatų būsenų skaičiaus sumažinimo problemomis.

Be to, automatas, kaip prietaisas, skirtas atlikti tikslingus veiksmus be žmogaus įsikišimo, yra laikomas arba įgyvendinančiu vieną ar kitą formaliąją gramatiką (abstraktus automatas), arba kaip elementų rinkinį ir jų sujungimo schemą (struktūrinis automatas).

Automatų teorija

Automatų teorija- diskrečiosios matematikos skyrius, studijuojantis abstrakčiuosius automatus - kompiuterius, pateiktus matematinių modelių pavidalu - ir problemas, kurias jie gali išspręsti.

Automatų teorija glaudžiausiai susijusi su algoritmų teorija: automatas diskrečią informaciją paverčia žingsniais į atskirus laiko momentus, o rezultatą formuoja duoto algoritmo žingsneliais.

Terminija

Simbolis- bet koks atominis duomenų blokas, galintis turėti įtakos mašinai. Dažniausiai simbolis yra raidė bendrine kalba, tačiau tai gali būti, pavyzdžiui, grafinis diagramos elementas.

  • Žodis- simbolių eilutė, sukurta sujungimo (sujungimo) būdu.
  • Abėcėlė- baigtinis skirtingų simbolių rinkinys (daug simbolių)
  • Kalba- žodžių rinkinys, sudarytas iš nurodytos abėcėlės simbolių. Gali būti baigtinis arba begalinis.
Mašina Mašina- penkių elementų seka (kortelė), kur: Žodis Automatas skaito galutinę simbolių eilutę a 1 ,a 2 ,…., a n , kur a i ∈ Σ, ir yra vadinamas žodį.Visų žodžių aibė rašoma kaip Σ*. Gautas žodis Žodį w ∈ Σ* priima automatas, jei q n ∈ F.

Sakoma, kad kalba yra L perskaityta (gauta) automatu M, jei jį sudaro žodžiai w pagal abėcėlę taip, kad jei šie žodžiai įvedami į M, apdorojimo pabaigoje jis patenka į vieną iš priimančių būsenų F:

Paprastai automatas pereina iš būsenos į būseną naudodamas perėjimo funkciją, skaitydamas vieną simbolį iš įvesties. Taip pat yra automatų, kurie gali pereiti į naują būseną neskaitydami simbolio. Šuolio funkcija neskaitant simbolio vadinama - perėjimas(epsilono perėjimas).

Taikymas

Praktikoje automatų teorija naudojama kuriant formaliųjų kalbų (įskaitant programavimo kalbas) lekserius ir analizatorius, taip pat kuriant kompiliatorius ir kuriant pačias programavimo kalbas.

Kitas svarbus automatų teorijos pritaikymas yra matematiškai griežtas problemų sprendžiamumo ir sudėtingumo nustatymas.

Tipiškos užduotys

  • Automatų konstravimas ir minimizavimas- abstraktaus automato sukūrimas iš tam tikros klasės, kuris išsprendžia duotą problemą (priima tam tikrą kalbą), galbūt vėliau sumažinant būsenų skaičių arba perėjimų skaičių.
  • Automatų sintezė- sistemos sukūrimas iš duotų "elementarių automatų", lygiaverčių tam tikram automatui. Toks automatas vadinamas struktūrinės. Jis naudojamas, pavyzdžiui, skaitmeninių elektros grandinių sintezei tam tikro elemento bazėje.

taip pat žr

Literatūra

  • Johnas Hopcroftas, Rajeevas Motwani, Jeffrey UllmanasĮvadas į automatų teoriją, kalbas ir skaičiavimą. - M .: Williams, 2002. - S. 528. - ISBN 0-201-44124-1
  • Kasjanovas V. N. Paskaitos apie formaliųjų kalbų teoriją, automatus ir skaičiavimo sudėtingumą. - Novosibirskas: NSU, 1995. - C. 112.

Nuorodos


Wikimedia fondas. 2010 m.

Pažiūrėkite, kas yra „Automatų teorija“ kituose žodynuose:

    Automatų teorija

    Automatų teorija- teorinės kibernetikos skyrius, tiriantis realių ar galimų įrenginių, kurie diskrečią informaciją apdoroja diskrečiaisiais ciklais, matematinius modelius (čia vadinamus automatais arba mašinomis). Pagrindinis ... ... Ekonomikos ir matematikos žodynas

    automatų teorija– Teorinės kibernetikos šaka, tirianti realių ar galimų įrenginių, kurie diskrečią informaciją apdoroja diskrečiaisiais ciklais, matematinius modelius (čia vadinami automatais arba mašinomis). Pagrindinės šios teorijos sąvokos ...... Techninis vertėjo vadovas

    Egzistuoja., Sinonimų skaičius: 1 tavt (1) ASIS Sinonimų žodynas. V.N. Trišinas. 2013... Sinonimų žodynas

    automatų teorija- automatų teorija statusas T sritis automatika atitikmenys: angl. automato teorija vok. Automatenteorija, f rus. automatų teorija, f pranc. theorie des automates, f … Automatikos terminų žodynas

    Šis terminas turi kitas reikšmes, žr. Būsenos diagramą. Būsenos diagrama yra nukreiptas baigtinio automato grafikas, kuriame viršūnės rodo lanko būsenas, rodo perėjimus tarp dviejų būsenų Praktikoje ... ... Vikipedija

    Mašinų ir mechanizmų teorija (TMM) – tai mokslinė disciplina apie bendruosius mechanizmų ir mašinų tyrimo metodus, konstravimą, kinematiką ir dinamiką bei apie mokslinius jų projektavimo pagrindus. Turinys 1 Drausmės raidos istorija 2 Pagrindinės sąvokos ... Vikipedija

    TEORIJA- (1) apibendrinančių mokslinių idėjų ir principų sistema Praktinė patirtis, atspindintis objektyvius prigimtinius įstatymus ir taisykles, kurios sudaro (žr.) arba bet kurio mokslo skyrių, taip pat taisyklių rinkinį bet kokių žinių srityje milijonai ... ... Didžioji politechnikos enciklopedija

    Algoritmų teorija Ekonomikos ir matematikos žodynas

    Algoritmų teorija– matematikos šaka, tirianti bendrąsias algoritmų savybes. Algoritmo su tam tikromis savybėmis konstravimo problema vadinama algoritmine problema, jos neišsprendžiamumas reiškia tinkamo algoritmo nebuvimą; jei…… Ekonomikos ir matematikos žodynas

Knygos

  • Automatų teorija. Vadovėlis bakalauro ir magistrantūros studijoms, Kudryavtsev V.B. Vadovėlyje yra daug medžiagos apie automatų teoriją. Jame pristatoma automato sąvoka, pateikiamos teorijos ...

Kiekvienas klausimas dedamas į vieną atskirą puslapį (išskyrus vieną – „KA algebrinė ir struktūrinė teorija“, kuris užima du puslapius). Cheat lapo formatas: doc.

Klausimai apie lovelę

  1. Automatų teorijos dalykas
  2. Automatų klasifikacija
  3. Automatų teorijos taikymai
  4. dvejetainis dauginimas
  5. Daugyba atvirkštiniais kodais
  6. Padalinys
  7. Padalijimas atvirkštiniais kodais. Ypatumai
  8. Operacijų atlikimo slankiojo kablelio formatu ypatybės
  9. Dvejetainiai dešimtainiai kodai. Papildymas DDC
  10. Diskretus keitiklis Gluškovo modelis
  11. Mikroprogramavimas
  12. Veikiančių mašinų konstrukcijos
  13. Procedūrinio tipo veikiančio automato (OA) sintezė
  14. OA struktūrinio tipo sintezė
  15. Automatinės kalbos. Oficialus automato pavedimas
  16. „Mealy“ ir „Moore“ modeliai
  17. Baigtinių automatų (FA) ekvivalentiškumas. Moore'o teorema
  18. Baigtinių automatų sumažinimas
  19. Mealy ir Moore mašinų lygiavertiškumas
  20. Valdymo mašinų tipai (UA)
  21. UA blokinės diagramos. Miles ir Moura
  22. Valdymo automato su standžiąja logika (UAZhL) sintezės etapai
  23. UAHL sintezės pavyzdžiai
  24. Lenktynės ir kaip su jomis elgtis
  25. UA su programuojama logika (PLL)
  26. KA algebrinė ir struktūrinė teorija
  27. Kelių UA sujungimas į vieną
  28. KA programinė įranga. Įgyvendinimo parinktys. Šablono būsena
  29. Paskyrimas ir trumpas aprašymas VHDL
  30. UA diegimas VHDL
  31. Suprasti UML modeliavimo kalbą
  32. Kalbų samprata ir formalioji gramatika
  33. Kalbos klasifikacija
  34. Siurblys Lemma
  35. NKI samprata. DCA gavimas per NCA
  36. Įprastos išraiškos. Sintaksės diagramos. Kleene teorema
  37. RV taikymas. Įvairūs RW žymėjimai
  38. COP-gramatikos ir nuspaudimo automatai
  39. Tiuringo mašinos
  40. MT naudojimas algoritmams analizuoti

Apgaulingo lapo klausimo pavyzdys

Automatų teorijos dalykas

Automatas yra objektas (idealas, medžiaga arba, tiksliau, įrenginys), kuris apdoroja informaciją.

Informacijos transformavimo metodų tyrimas yra automatų teorijos dalykas plačiąja prasme.

Automatų teorija yra kibernetikos, kaip mokslo apie informacijos saugojimo, suvokimo, perdavimo ir apdorojimo mašinose ir gyvuose organizmuose būdus, dalis.

Automatų teorija naudoja įvairius matematinius modelius. Labiausiai paplitę iš jų yra tiriami abstrakčioji teorija automatai ir algebrinė TA.

Abstrakčiosios TA požiūriu automatas yra rinkinių ir atvaizdų rinkinys. Pavyzdžiui, automatas gali būti apibrėžtas kaip šešių objektų: A = , kur:

  • X yra automato įvesties simbolių rinkinys
  • Y yra automato išvesties simbolių rinkinys
  • Q yra automato būsenų rinkinys
  • q0 yra pradinės automato būsenos
  • A – perėjimo funkcija: Q x X –> Q
  • B yra išvesties funkcija: Q x X -> Y

Automato transformacijos: automato išvesties žodžiai priklauso ne tik nuo būsenų išvesties žodžių, bet ir nuo ankstesnės būsenos žodžių reikšmių.

Matematinis automatas kartais laikomas algebra, išskiriamas automato būsenų ir operacijų rinkinys šioje aibėje.

Techninis automatas yra fizinis įrenginys, kuriam svarbus ne tik elgesys ar veikimo dėsnis, bet ir jo vidinė struktūra, gaudama šią struktūrą, todėl technologijoje jie laiko automato konstrukcijos teoriją, kurios objektas yra automato sandaros tyrimas, automato grandinių su nurodytomis savybėmis analizė ir sintezė.

Galima išskirti šiuos automatų teorijų tipus:

  • Santrauka TA (matematinė);
  • Struktūrinė TA (techninė);
  • Bendroji TA;
  • Taikomoji TA;

PTCA – diskretinis automatas – įrenginys, konvertuojantis skaitmeninę informaciją pagal nurodytą algoritmą.

TT automatas – įrenginys, atliekantis įvesties žodžių (teksto) transformaciją (atpažinimą).

AUTOMATŲ TEORIJA.

ĮVADINĖS NUOSTATOS.

Automatų teorija- diskrečiosios matematikos skyrius, tiriantis realių (techninių, biologinių, ekonominių) ar galimų įrenginių, apdorojančių diskrečią informaciją diskrečiaisiais laiko žingsniais, matematinius modelius.

Šioje teorijoje jos kryptys yra gana aiškiai nustatytos dėl:

    tiriamų automatų tipų parinkimas (baigtinis, begalinis, deterministinis, tikimybinis, autonominis, kombinacinis, be išvesties)

    priimtas abstrakcijos lygis (abstrakčiai ir struktūriniai automatai)

    taikomosios matematikos specifika (algebrinė automatų teorija)

Tuo pačiu metu nagrinėjamų objektų diskrečiuose modeliuose atsižvelgiama tik į vykstančių automato pokyčių procesų logiką, neatsižvelgiant į kiekybines charakteristikas.

Centrinės skaitomos teorijos problemos yra sintaksės ir analizės problemos (t.y. automato funkcinės schemos sukūrimas pagal duotą elgseną ir automato elgesio aprašymas pagal žinomą struktūrą). Šios problemos yra glaudžiai susijusios su pilnumo, lygiavertiškumo ir automatų būsenų skaičiaus sumažinimo problemomis.

Be to, automatas, kaip prietaisas, skirtas atlikti tikslingus veiksmus be žmogaus įsikišimo, yra laikomas arba įgyvendinančiu vieną ar kitą formaliąją gramatiką (abstraktus automatas), arba kaip elementų rinkinį ir jų sujungimo schemą (struktūrinis automatas).

Pagrindinės automatų teorijos sąvokos

    Abstrakčios būsenos mašinaU- modelis , vaizduojantis įrenginį, kuris konvertuoja informaciją pagal taisykles R „juodosios dėžės“ pavidalu su įvesties A ir išvesties B abėcėlėmis, taip pat kai kuriais rinkiniais. vidines būsenas K.

a i  A , b j  B, q k  Q

Kai į įėjimą nukreipiamas signalas a i, tai, priklausomai nuo jo ir esamos būsenos q k  Q, automatas pereina į kitą būseną q l  Q ​​ir duoda signalą į išėjimą b j  B. Tai vienas ciklas automato q k a i  q l b j . Tada duodamas kitas signalas, prasideda kitas ciklas ir pan. Įvesties signalo pasikeitimas keičia automato būseną, o jo išėjimo signalas reiškia elementarią signalų pavidalu gaunamos informacijos transformaciją.

    Begalinė mašina yra abstraktus automatas, bent viena iš apibrėžiančių aibių A, B, kurios Q yra begalinis.

    Sitochastinis (tikimybinis) automatas- abstraktus automatas, informacijos transformavimo taisyklės, kurių R yra tikimybinės.

    valstybės mašina yra diskretiškas automatas, kuriame perėjimas iš vienos būsenos į bet kurią kitą gali būti baigtas per baigtinį žingsnių skaičių (toks automatas, pavyzdžiui, yra procesorius).

    Konstrukcinis automatas- baigtinių būsenų mašina, kurios vidinė struktūra žinoma.

    Formali gramatika = - taisyklių sistema P konstravimui duotoje abėcėlėje TH(T – galinė abėcėlė, H – negalinė abėcėlė, TH=) baigtinių ženklų sekų, kurių aibė sudaro tam tikrą formalią kalbą () (JH, H yra aksioma ).

    formalią kalbą- kalba, sukurta pagal tam tikro loginio skaičiavimo taisykles (kitaip tariant, kalba, kurios sintaksę apibrėžia formali gramatika ).

    Žodis– simbolių eilutė tam tikroje abėcėlėje (įprasta eilutes žymėti abėcėlėje (TH)) Graikiškos raidės; taigi, pavyzdžiui,  (TH)*).

    Sakinys yra termino abėcėlės žodis.

    Gamyba (sintaksinė taisyklė)– būdas  (, ,  (TH)*) formos grandinę paversti  ((TH)*) formos grandine.

    Išvesties medis (analizavimas)- tam tikros gramatikos sakinio išvesties vizualinio vaizdavimo forma.

AUTOMATAI IR FORMALIOS KALBOS.

Formalių kalbų (kaip baigtinių ar begalinių žodžių rinkinių) aprašymas baigtinėmis priemonėmis atliekamas tiek automatais, tiek formaliosiomis gramatikomis.

Kalbos tipas () pagal Chomsky

Chomsky formaliosios gramatikos tipą

Automatinis kalbos modelis

Savavališka (algoritminė) 0 tipo gramatika 

Turingo mašina

1 tipo gramatika (kontekstinė gramatika, N.C. gramatika, greitoji gramatika)

Automatas su tiesiškai ribota atmintimi

2 tipo gramatika (be konteksto gramatika, C.S. gramatika, be konteksto gramatika) B

Automatinis žurnalas

3 gramatikos tipas (automatinis, įprastas, baigtinis)

BaC, Ba

valstybės mašina

Kalbų klasės pagal Chomsky yra hierarchija, t.y. 3 tipo kalba yra 2 tipo kalbos poklasis, t.y. ( 3) ( 2) ( 1)  ( 0). Remiantis žemiau pateikta lentele, galima teigti, kad

    taisyklingą kalbą (t. y. kalbą, kurią generuoja 3 tipo gramatika) atpažįsta baigtinis automatas ir šiuo požiūriu yra paprasčiausia matematiškai

    bekontekstinė kalba (t. y. kalba ( 2)) atpažįstama nuspaudimo automatu, begaliniu automatu, kurio vidinė struktūra yra kamino atmintis

    konteksto kalbą ( 1) atpažįsta automatas su tiesiškai ribojančia atmintimi, t.y. automatas, kuriam norint atpažinti nN ilgio seką, reikia ne didesnės kaip k * n atminties, kur k yra skaičius, nepriklausomas nuo įvesties žodžio

    savavališka formali kalba, t.y. ( 0), atpažįstama Tiuringo mašinos - matematinė sąvoka formaliai patobulinti intuityvią „algoritmo“ sąvoką

komentuoti: Sintaksės taisyklėje B yra kontekstai (kairėje ir dešinėje), kurie gali būti tuščios eilutės; VN, a,, ,   (TN).

FORMALIOJI GRAMMATIKA.

Formaliosios gramatikos = kaip galima sukurti ir atpažinti procedūras. Generatyvinė gramatika iš esmės yra ypatingas formalios sistemos FS / = atvejis<, D>-=. Šiuo atveju A=TH, F(TH) * , JH, P= i  j  i , j  N ,  i ,  j (TH) * , tie. išvedžiojimo taisyklės P leidžia gauti termininės abėcėlės T žodžius iš vienintelės aksiomos J, pakeičiant negalinius stygų simbolius abėcėlėje (TH).

Gramatikos atpažinimas yra algoritmas, kuris bet kuria grandine atpažįsta, ar tai kalbos  T * žodis.

Žodžių atpažinimo ir generavimo automatas gali būti laikomas įvesties simbolių eilučių apdorojimo įrenginiu, kurio tikslas:

    jų priklausymo formaliai kalbai nustatymas ()

    kartos išvesties simbolių eilutes

Išvada gramatikoje  yra grandinių seka, kurioje kiekviena iš grandinių, išskyrus pirmąją, gaunama iš ankstesnės, taikant kokią nors išvados taisyklę  (paskutinė grandinė išvestyje yra sakinys, t. y. žodis B abėcėlėje T).

1 pavyzdys: T=a, b, c, H=B, C, J=B, P=BaBC, BCc, Cb

Galima šios gramatikos išvestis gali būti žodžių seka:

B, аBC, аСсС, abсС, abсbT *

Ši gramatika generuoja kalbą b, bc, abcb.

2 pavyzdys: nelyginių skaičių aibė unarinėje vaizde yra a, aaa, aaaaa….. formos galinių žodžių rinkinys, t.y. kalba =xT * : xa 2 n -1 , nN. Šią kalbą generuoja automatinė gramatika  3 =<a, J, J, Ja, JaB, BaJ>.

3 pavyzdys: Kalba =xT * : x=a n b n  n  N generuoja K.S. gramatikos, t.y.  2 =<a, b, J, J, JaJb, Jab>.

4 pavyzdys: Būlio formulių su kintamaisiais x, y, z kalbą generuoja K.S. gramatika  2 =<x, y, z, , , , (,), J, J, J(JJ), J(JJ), JJ, Jx, Jy, JZ>.

PASIŪLYMAS EKSPLOATORIUS.

Praktikoje kalbos () žodžius išvesti kaip eilučių seką dažnai būna sudėtinga. Be to, šis metodas neleidžia gauti informacijos apie sintaksines konstrukcijas patogia forma. Geriausias būdas kompaktiškai pavaizduoti žodžių išvestį šiuo atveju yra išvesties medis (analizavimo medis, analizavimo medis). Jie sako, kad standartinis išvadų medis pateikiamas, jei taisyklė r i:  1 A 2  1  2, (TH) *) yra susieta su elementariu pomedžiu t(r i) su viršūne A ir vainiku.  1  2.

Pavyzdys 1 : Tegu 1=<a, b, c, A, B, C, D, J, J, JAAB, ABDBB, aBBabB, Aa, Da, BC, Cc>.

J, AAB, aAB, aDBB, aaBB, aabB, aaaBC, aabc išvestis pavaizduota medžiu:

Čia J yra medžio šaknis, J A , A a yra pomedžiai.