Rendszeres nyelvek és nyelvtanok
Adott véges ábécé
és így a készlet minden véges szavak ábécé:
.
Formális nyelv az ábécé - egy tetszőleges részhalmaza.
A szabályrendszer kialakítására szó hivatalos nyelv az úgynevezett a nyelvtan. Attól függően, hogy a szabályok bonyolultsága formális nyelvek vannak osztva osztályok száma. Ezután vesszük az egyik legegyszerűbb nyelvórákon - reguláris nyelvek - és bevezessék kapcsolatban véges automaták.
Fontolja meg a készlet nyelvek ugyanolyan ábécé és vezessen műveletek a következő nyelveken.
1 °. Egyesület. Ez halmazelméleti művelet, amely, ellentétben a kereszteződést, és kiegészítője, amelynek természetes szintaktikai értelmezést:
.
2 °. Összefűzése - egy társított műveletet helyettesítése a nyelvet a nyelv:
.
3 °. Iteráció által meghatározott nyelven
,
ahol - a nyelvet, mely üres szavak, ami nem tévesztendő össze egy üres nyelvet. nem tartalmaz egyetlen szót; . . ...
Nyelven. . álló üres, vagy egy-betűs szavak nevezzük elemi.
A nyelv az úgynevezett szabályos. ha lehet kialakítani egy véges számú egyesítési műveletek, összefűzés és iteráció.
35. Az állam gép nevezzük Moore automata. Ha a kimeneti funkció csak attól függ állapota:
.
Az általános modell egy véges állapotú gép, amely már korábban feltételezték, nevezzük automata Millie.
Annak ellenére, hogy a gép Milli - egy speciális esete az Moore gép, a lehetőséget a két gép ugyanaz.
Tétel. Bármely gép Milli létezik ekvivalens Moore automata.
Tekintsük a Moore gép két kimeneti jelek 0 és 1.Takoy gép, hogy néhány bemeneti szavakat 1 a másik - 0. Tegyük fel, hogy az első esetben a gép „elismert” szót, és a második - nem. Ez határozza meg, egyes nyelvi szavakból tevődik össze, amelyek automatikusan felismeri.
Osztjuk a Moore állam gép két osztályba - a kimenet értéke 1, az osztály - a kimenet 0. Ez lehetővé teszi, hogy nem tekinti a funkció kilép és meghatározzák automata-feloldó, mint rendszer
.
Minden gép szánunk nekik egy felismerhető nyelven
,
azaz egy nyelv áll minden szó, hogy lefordítani egyik automatikus zárás a kezdeti állapot.
Példa. . hol. . . . és beállítja az asztalra