Konačni automati i regularni jezici. Metode za definiranje regularnih jezika Definicija regularnog jezika
Laboratorijski rad br.3
Razvoj leksičkog analizatora prilično je jednostavan ako se koristi teorija regularnih jezika i konačnih automata. U okviru ove teorije, klase leksema istog tipa smatraju se formalnim jezicima (jezik identifikatora, jezik konstanti, itd.), čiji je skup rečenica opisan pomoću odgovarajuće generativne gramatike. Štoviše, ovi jezici su toliko jednostavni da su generirani najjednostavnijom gramatikom - regularnom gramatikom.
Definicija 1. generativna gramatika G =
Jezik L (G) generiran automatskom gramatikom naziva se automatski (regularni) jezik ili jezik s konačnim brojem stanja.
Primjer 1. Klasa identifikatora, ako je identifikator niz koji se sastoji od slova i brojeva, a prvi znak identifikatora može biti samo slovo, opisuje se sljedećom generativnom regularnom gramatikom G =
N= (I, K), T = (b, c), S=(I),
P = ( 1. I::= b
Ovdje su b, c generalizirani terminalni simboli za označavanje slova odnosno brojeva.
Proces generiranja identifikatora "bbcbc" opisan je sljedećim nizom zamjena
I => bbc => bbc => bbcK => bbcbK => bbcbc
Međutim, glavna zadaća LA nije generiranje leksičkih jedinica, već njihovo prepoznavanje. Matematički model procesa prepoznavanja regularnog jezika je računalni uređaj koji se naziva konačni stroj (FA). Izraz "konačan" naglašava da računalni uređaj ima fiksnu i konačnu količinu memorije i obrađuje niz ulaznih simbola koji pripadaju nekom konačnom skupu. Postoje razne vrste KA, ako je izlazna funkcija KA (rezultat rada) samo pokazatelj je li ulazni niz simbola prihvatljiv ili ne, takav KA se naziva konačni razrješivač.
Definicija 2. Sljedećih pet naziva se konačnim automatom:
A =
Q = (q 0 , q 1 , …, q n -1 ) – abeceda stanja (konačan skup simbola);
δ: Q ×V →Q – prijelazna funkcija;
q 0 Ê Q – početno stanje konačnog automata;
F Ê Q – skup konačnih stanja.
Shema rada svemirske letjelice.
Postoji beskonačna traka, podijeljena na ćelije, od kojih svaka može sadržavati jedan simbol iz V. Lanac α Ê V* je napisan na traci. Ćelije lijevo i desno od lanca su prazne. Postoji uređaj za završnu kontrolu (FCU) s glavom za čitanje, koja može sekvencijalno čitati znakove s vrpce, krećući se po vrpci s lijeva na desno. U tom slučaju upravljačka jedinica može biti u bilo kojem stanju od Q. Kontrolna jedinica uvijek počinje svoj rad u početnom stanju q 0, a završava u jednom od završnih stanja F. Svaki put, prelazeći na novu ćeliju na trake, upravljačka jedinica prelazi u novo stanje u skladu s funkcijom δ.
Prijelazna funkcija svemirske letjelice može se prikazati na sljedeće načine:
· Skup timova;
· Dijagram stanja;
· Prijelazna tablica.
Naredba stroja stanja je napisana na sljedeći način:
(q i, a j) → q k, gdje su q i, q k Ê Q; a j Ê V.
Ova naredba znači da je automat stanja u stanju q i, čita simbol a j s trake i prelazi u stanje q k.
Grafički se naredba prikazuje kao luk grafa koji ide od vrha q i do vrha q k i označen je simbolom a j ulazne abecede:
Grafički prikaz cjelokupnog preslikavanja δ naziva se dijagram stanja konačnog automata.
Ako se letjelica nađe u situaciji (q i, a j), koja nije lijeva strana nijedne naredbe, tada se zaustavlja. Ako kontrolna jedinica prebroji sve simbole lanca α snimljene na vrpci, a istovremeno ide u konačno stanje q r Ê F, tada kažu da je lanac α dopušten od strane konačnog automata.
Prijelazna tablica svemirske letjelice konstruirana je na sljedeći način: stupci matrice odgovaraju simbolima iz ulazne abecede, redovi odgovaraju simbolima iz abecede stanja, a elementi matrice odgovaraju stanjima u koja letjelica ide za zadanu kombinaciju ulaznog simbola. i državni simbol.
Neka je regularna gramatika G =
Tada je konačni automat A =
2) Q = N U (Z), Z N i Z T, Z je konačno stanje letjelice;
5) Preslikavanje δ je konstruirano u obliku:
· Svako supstitucijsko pravilo u gramatici G oblika A i::= a j A k pridružuje se naredbi (A i, a j) → A k;
· Svako pravilo zamjene oblika A i::= a j pridružuje se naredbi (A i, a j) → Z;
Primjer 2. Konstruirajte CA za gramatiku iz primjera 1. Imamo A =
1) V = T = (b, c)
2) Q = N U (Z) = (I, R, Z)
3) q 0 = (S) = (I)
5) δ: a) u obliku skupa naredbi:
b) u obliku dijagrama stanja
Postoje deterministički i nedeterministički konačni automati. Svemirska letjelica se zove nedeterministički KA (NKA), ako u njegovom dijagramu stanja iz jednog vrha izlazi više lukova s identičnim oznakama. Na primjer, KA iz primjera 2 je NKA.
U praktične svrhe potrebno je da završni prepoznavač sam odredi trenutak u kojem završava ulazni niz znakova i izda poruku o ispravnosti ili pogrešci unosa niza. U ove svrhe, ulazni lanac se smatra ograničenim s desne strane krajnjim markerom ├, a interpretirana stanja se unose u dijagram stanja svemirske letjelice:
Z – “dopusti lanac unosa”;
O – „zapamćena je pogreška u lancu unosa”;
E – "odbaci lanac unosa."
Stanja Z i E su konačna, a svemirska letjelica ide u njih kada očitava oznaku kraja ├, odnosno nakon obrade ispravnog ili pogrešnog lanca unosa. Stanje O je srednje, letjelica prelazi u njega iz bilo kojeg valjanog stanja letjelice kada se otkrije pogreška u ulaznom lancu i ostaje tamo dok ne stigne krajnji marker ├, nakon čega prelazi u stanje E - „odbaci ulazni lanac. ”
U ovom poglavlju počinjemo predstavljati elemente teorije formalnih jezika.
Kada kažemo "formalni jezik", mislimo na to da se ovdje predstavljeni rezultati prvenstveno koriste u opisivanju umjetnih jezika koje su izmislili ljudi za posebne svrhe, kao što su programski jezici. Ali ne postoji nepremostiva prepreka između posebno izmišljenih umjetnih (formalnih) jezika i prirodnih jezika koji spontano nastaju i razvijaju se. Ispada da prirodne jezike karakteriziraju složena gramatička pravila, tj. su prilično rigidno formalizirani, a čak i "znanstveno najrazvijeniji" programski jezik sadrži "tamna mjesta", čije nedvosmisleno razumijevanje predstavlja problem.
Tri su glavna aspekta koja morate imati na umu kada učite jezike.
Prvi je jezična sintaksa . Jezik je neka vrsta skupa "riječi", gdje je "riječ" određeni konačni niz "slova" - simbola neke unaprijed utvrđene abecede. Pojmovi "slovo" i "riječ" mogu se razumjeti na različite načine (matematička definicija ovih pojmova bit će dana u nastavku). Dakle, "slova" zapravo mogu biti slova abecede nekog prirodnog ili formalnog jezika, na primjer, ruskog jezika ili programskog jezika Pascal. Tada će "riječi" biti konačni nizovi "slova": krokodil, " cijeli broj". Takve se riječi nazivaju "leksemima". Ali "slovo" može biti "riječ" ("leksem") kao cjelina. Tada su "riječi" rečenice prirodnog jezika ili programa programskog jezika. Ako neki skup "slova" fiksirana, onda neće svaki njihov niz biti "riječ", tj. eleksem određenog jezika, već samo niz koji poštuje određena pravila. Riječ "krykadil" nije leksem u ruskom, a riječ "iff" nije leksem u Pascalu. Rečenica "Volim te" nije ispravna rečenica na ruskom, baš kao što oznaka "x:= =t" nije ispravno napisan Pascal operator dodjele. Sintaksa* jezika je sustav pravila u skladu s kojima se mogu konstruirati "ispravni" nizovi "slova". Svaku riječ nekog jezika karakterizira određena struktura specifična za taj određeni jezik. Tada je potrebno, s jedne strane, razviti mehanizme za nabrajanje, odnosno generiranje riječi sa zadanom strukturom, as druge strane, mehanizme za provjeru pripadnosti date riječi određenom jeziku. Prije svega, upravo te mehanizme proučava klasična teorija formalnih jezika.
Drugi aspekt - semantika jezika . Semantika** uključuje povezivanje riječi nekog jezika s određenim "značenjem", Značenjem." Na primjer, kada pišemo matematičku formulu, moramo slijediti određena sintaktička pravila (stavljanje zagrada, pisanje simbola, redoslijed simbola itd.). ), ali, osim toga, formula ima vrlo određeno značenje, znači nešto.
Jezik je sredstvo komunikacije i prijenosa informacija. Ako želimo da budemo shvaćeni, moramo ne samo sintaktički ispravno graditi svoj govor, pazeći na pravilan redoslijed slova u riječi i riječi u rečenici, nego moramo voditi računa o njegovom značenju, o idejama koje izražavamo u govoru. Matematičke teorije "značenja" pojavile su se relativno nedavno, a uz sljedeće poglavlje vrlo kratko ćemo se osvrnuti na neke pristupe matematičkom opisu semantike programskih jezika.
* Riječ "sintaksa" dolazi od starogrčkog "syn" - "zajedno" i "taxis" - "red, struktura". Dakle, sintaksa se može shvatiti kao "kompozicija".
** Od starogrčkih riječi “sema” - “znak, predznak” i “semanticos” - “označavanje”.
Konačno, treći aspekt - pragmatika jezika . Pragmatika je povezana s ciljevima koje si izvorni govornik postavlja: na primjer, osoba izgovara govor s ciljevima koji se ne odnose na sintaksu, ne na semantiku jezika na kojem govori ili piše, već, recimo, na primanje određeni iznos novca za svoj govor količine novca. Pragmatika je prije socio-filozofska disciplina koja utječe na aktivnost postavljanja ciljeva pojedinca. Nećemo ga ni najmanje dirati.
U ovom će se poglavlju prvo ispitati temeljni koncepti matematičke teorije formalnih jezika, među kojima je najvažniji koncept generativne gramatike, a potom i tzv. regularni jezici. Teorija regularnih jezika, zajedno s teorijom konačnih automata, čini temelj cjelokupne teorije formalnih jezika.
Abeceda, riječ, jezik
Generativne gramatike
Kao što je već navedeno, klasična teorija formalnih jezika prvenstveno proučava sintaksu jezika. Uvodi matematički model sintakse koji opisuje mehanizme za generiranje i prepoznavanje "dobro oblikovanih" lanaca. U ovom dijelu ćemo pogledati prvi od ovih mehanizama.
Uobičajeni jezik
U teoriji jezika redoviti set(ili, na redovnom jeziku) naziva se formalni jezik koji zadovoljava sljedeća svojstva. Ova jednostavna svojstva su takva da je klasu regularnih skupova pogodno proučavati kao cjelinu, a dobiveni rezultati primjenjivi su u mnogim važnim slučajevima formalnih jezika. To jest, koncept pravilnog skupa je primjer matematičke strukture.
Definicija regularnog skupa
Neka je Σ konačna abeceda. Redovni set R(Σ) u abecedi Σ definiran je sljedećim rekurzivnim svojstvima:
| №. | Vlasništvo | Opis |
| 1 | Prazan skup je pravilan skup u abecedi Σ | |
| 2 | Skup koji se sastoji od samo jednog praznog niza je pravilan skup u abecedi Σ | |
| 3 | Skup koji se sastoji od bilo kojeg simbola abecede Σ je pravilan skup u abecedi Σ | |
| 4 | Ako su bilo koja dva skupa regularna u abecedi Σ, tada je i njihova unija regularan skup u abecedi Σ | |
| 5 | Ako su bilo koja dva skupa regularna u abecedi Σ, tada je skup sastavljen od svih mogućih kombinacija parova njihovih elemenata također regularan skup u abecedi Σ | |
| 6 | Ako je bilo koji skup regularan u abecedi Σ, tada je skup svih mogućih kombinacija njegovih elemenata također regularan skup u abecedi Σ | |
| Ništa osim sljedećeg nije pravilan skup u abecedi Σ |
vidi također
- Izgradnja parsera na temelju automatskog pristupa
Zaklada Wikimedia. 2010. godine.
Pogledajte što je "običan jezik" u drugim rječnicima:
regularni jezik- - Telekomunikacijske teme, osnovni pojmovi EN uobičajeni jezik... Vodič za tehničke prevoditelje
- (latinski regularius, od regula pravilo). Ispravan, korektno posložen, napravljen. Redoviti rad stroja. Čak i moždani udar. Redovan život. Korektan, pristojan, monoton život. Rječnik stranih riječi uključenih u ruski jezik.... ... Rječnik stranih riječi ruskog jezika
Cm… Rječnik sinonima
Drevni pisani jezik- Jezik duge pisane tradicije, odnosno dobio je pisani jezik prilagođen strukturi određenog jezika prije nekoliko stoljeća, a funkcioniranje pisane inačice jezika nije bilo epizodno, već redovno, uz... . .. Rječnik sociolingvističkih pojmova
Ovaj izraz ima i druga značenja, vidi Quechua. Quechua samoime: Qhichwa Simi, Runa Simi Zemlje ... Wikipedia
Okvir zgrade s mrežom stupova ili stupova koji se temelje na stepenici iste veličine (bugarski; bʺlgarski) uniformni kostur (češki; češtinski) pravidelný kostur (njemački; njemački) regelmäßiges Skelett (mađarski; mađarski) szabályos... ... Građevinski rječnik
- [FRANCUSKI PARK] park koji ima geometrijski pravilan tlocrt, obično osni tlocrt (bugarski; bʺlgarski) frenski park (češki; češtinski) francouzský park (njemački; njemački) regelmäßiger Park; Französischer park…… Građevinski rječnik
Quechua Samoime: Qhichwa Simi, Runa Simi Zemlje: Argentina, Bolivija, Kolumbija, Peru, Čile, Ekvador Regije: Ande Službeni status: Peru ... Wikipedia
Tagalog jezik- (tagal, tagala, tagalo; tagalog) jedan od filipinskih jezika. Područje inicijalne rasprostranjenosti nalazi se u politički, ekonomski i kulturno najvažnijoj regiji Republike Filipini - središnji i južni dio otoka... ... Lingvistički enciklopedijski rječnik
knjige
- Izvedeni glagoli. Tajne finske gramatike. Udžbenik, Safronov V.D.. Priručnik je posvećen jednom od najzanimljivijih i nedovoljno predstavljenih odjeljaka finske gramatike u obrazovnoj literaturi na ruskom jeziku - izvedenim glagolima. Tvore se od glagola i od imena...
Regularne gramatike, konačni automati i regularni skupovi (i regularni izrazi koji ih predstavljaju) tri su različita načina određivanja regularnih jezika.
Izjava
Jezik je PM ako i samo ako je određen lijevo-linearnom (desno-linearnom) gramatikom. Jezik se može definirati lijevo-linearnom (desno-linearnom) gramatikom ako i samo ako je regularan skup.
Jezik je PM ako i samo ako ga određuje konačni stroj. Stroj stanja prepoznaje jezik ako i samo ako je on PM.
Sve ove tri metode su ekvivalentne. Postoje algoritmi koji omogućuju, za jezik definiran na jedan od ovih načina, konstruiranje druge metode koja definira isti jezik. Detaljan opis ovih algoritama dostupan je u literaturi (vidi popis).
Na primjer, da bi se pronašao regularni izraz za jezik definiran desnolinearnom gramatikom, potrebno je konstruirati i riješiti sustav jednadžbi s regularnim koeficijentima.
U teoriji programskih jezika najvažniju ulogu ima ekvivalencija CA i regularnih gramatika, budući da se takve gramatike koriste za definiranje leksičkih struktura programskih jezika. Stvaranjem automata na temelju poznate gramatike dobivamo prepoznavač za dati jezik. Na taj način moguće je riješiti problem raščlanjivanja leksičkih konstrukcija jezika.
Da bi se konstruirao CA temeljen na poznatoj regularnoj gramatici, mora se svesti na automatski oblik. Skupu stanja automata odgovarat će skup neterminalnih simbola gramatike. 2.3.2 Svojstva regularnih jezika
Skup se naziva zatvorenim prema nekoj operaciji ako se kao rezultat izvođenja te operacije nad bilo kojim njegovim elementom dobije novi element koji pripada istom skupu.
Regularni skupovi su zatvoreni pod operacijama presjeka, unije, dodavanja, ponavljanja, ulančavanja, mijenjanja imena simbola i zamjene nizova za simbole.
Za obične jezike mogu se riješiti mnogi problemi koji su nerješivi za druge vrste jezika. Na primjer, sljedeći problemi su rješivi bez obzira na to kako je naveden jezik:
Problem ekvivalencije: data su dva regularna jezika L 1 (V) i L 2 (V). Potrebno je utvrditi jesu li ekvivalentni.
Problem lančane pripadnosti jeziku. Zadan regularni jezik L(V), niz simbola V * . Moramo provjeriti pripada li ovaj lanac jeziku.
Problem praznine jezika. S obzirom na regularni jezik L(V). Potrebno je provjeriti da li je ovaj jezik prazan, tj. pronaći barem jedan lanac, L(V).
Ponekad je potrebno dokazati je li određeni jezik pravilan. Ako je moguće specificirati ovaj jezik na jedan od razmatranih načina, onda je on regularan. Ali ako se takva metoda ne može pronaći, nepoznato je je li jezik nepravilan ili jednostavno nije bilo moguće pronaći način da se to odredi. Postoji jednostavna metoda za provjeru je li dotični jezik pravilan. Dokazano je da ako je za određeni jezik tzv lema proširenja, onda je regularna. Ako ova lema nije zadovoljena, jezik nije regularan.
Lema rasta je formulirana na sljedeći način. Ako je dan regularni jezik i dovoljno dug lanac simbola koji pripada tom jeziku, tada se u njemu može naći neprazan podniz koji se može ponoviti koliko god puta se želi, a svi lanci dobiveni na ovaj način također će pripadati regularni jezik u pitanju.
Formalno, lema je napisana na sljedeći način. Ako je dan jezik L, tada je konstanta p>0 takva da ako su L i p, tada se lanac može napisati u obliku gdje je 0 Primjer. Razmotrimo jezik L=(a n b n n>0). Dokažimo da to nije regularno, koristeći se lemom o širenju jezika. Neka je ovaj jezik regularan, tada za njega mora vrijediti lema proširenja. Uzmimo neki lanac ovog jezika = a n b n i napišimo ga u obliku. Ako je a + ili b + , tada lanac i ne pripada jeziku ni za jedno i, što je u suprotnosti s uvjetima leme. Ako je a + b + , tada ni lanac 2 ne pripada jeziku L. Dobili smo kontradikciju, dakle, jezik nije regularan. Teorija automata
- ovo je dio teorije sustavi upravljanja, proučavajući matematičke modele diskretnih pretvarača informacija, tzv strojnice. S određene točke gledišta, takvi pretvarači su i stvarni uređaji (računala, automati, živi organizmi itd.) i apstraktni sustavi (na primjer, formalni sustav, aksiomatske teorije itd.), što omogućuje primjenu teorije automata u raznim znanstvenim i primijenjenim istraživanjima. Teorija automata najuže je povezana s matematičkom logikom i teorijom algoritama. Konkretno, pomoću teorije automata dokazuje se rješivost nekih formalnih računa. Još jedan važan predmet proučavanja ovog kolegija je formalni jezik
1
– proizvoljan skup riječi neke abecede. Važnost formalnih jezika za teorijsku informatičku znanost je zbog činjenice da je najjednostavniji i najprikladniji model podataka koji se koristi u računalnim programima konačni niz, čiji je svaki element preuzet iz nekog unaprijed fiksnog konačnog skupa. Budući da su formalni jezici koji se koriste u aplikacijama obično beskonačni, potreban je način da se formalni jezik opiše na konačan način. U ovom tečaju proučavat ćemo 3 klasična načina ovog opisa: strojnice,
regularni izrazi I generativne gramatike. Promotrimo neprazan konačni skup A, koji se sastoji od znakova ( a 1 ,
…, a k). Nazvat ćemo A
abeceda
, a njegovi simboli su slova
.
Bilo koji konačni niz slova ove abecede naziva se u jednoj riječi
(lanac
ili crta
):
w=a 1 a 2 …a n- riječ ( a ja
A),
|w| – duljina riječi (broj slova koja čine riječ, pri čemu se svaki znak pojavljuje onoliko puta koliko se pojavljuje u w). Preko | w| b označimo broj pojavljivanja simbola b po riječi w. Beskonačan niz slova abecede A nazvao nadriječ
, - nadriječ od beskonačnog broja slova A.
Prazan
je riječ koja ne sadrži niti jedno slovo. Označava se sa . Očito ||=0. Bilo koji podskup Ako x I g– riječi jezika Kažu da riječ x
– podriječ
riječi na, Ako g=uxv za neke riječi u I v. Sve podriječi riječi u jeziku Primjeri.
1. ba 3 =baaa,
2. Postavite ( a,
abb) - jezik (konačni) preko abecede ( a,
b}. 3. Puno Budući da je svaki jezik skup, možemo razmotriti operacije unije, presjeka i razlike jezika definiranih preko iste abecede. Da, jezik Neka Primjeri. 1. Ako 2. Ako je L=(0, 01), tada Ponavljanje
Jezik L zvan jezik Primjer. Ako A={a,
b) I L={aa,
ab,
ba,
bb), To Žalbom
ili u zrcalnoj slici
riječi w riječ se zove w R, u kojem su slova riječi w idite obrnutim redom. Na primjer, ako w=bac, To Neka Nazvat ćemo svaki početak riječi prefiks
, i svaki kraj riječi - sufiks
. Na primjer, ako g=xv, To x– prefiks riječi na(oznaka – x[g), A v– nastavak riječi na(oznaka – v]g). Očito, prazna riječ je i prefiks i sufiks bilo koje riječi. Svi prefiksi riječi u jeziku Ako jezik L takav da nema riječi L nije prefiks (sufiks) bilo koje druge riječi L, onda to kažu L ima prefiks
(sufiks) imovine
. Neka A 1 i A 2 – abecede. Ako prikaz f:
Bilješke. 1. Može se dokazati da ako f je onda homomorfizam 2. Homomorfizmi nisu uvijek bijekcije, ali svaki homomorfizam je jedinstveno određen svojim značenjem na riječi od jednog slova. 3. Primjena homomorfizma na jezik L, dobivamo drugi jezik f(L). Ako f:
Primjeri. 1. Recimo da želimo svako pojavljivanje znaka 0 u nizu zamijeniti znakom A, a svako pojavljivanje 1 je uključeno bb. Tada možemo definirati homomorfizam f Tako 2. Neka f je homomorfizam za koji Uvod
1. Osnovni pojmovi teorije formalnih jezika
- mnoge riječi abecede A duljina n. Skup svih riječi abecede A(uključujući superriječi). A*. Ovaj skup je prebrojiv jer je unija prebrojivog broja konačnih skupova 
. Skup svih nepraznih riječi u abecedi A označen sa A+ . Ako A={a), To A*={a)* bit će označen sa A*.
nazvao jezik
(formalni jezik
) iznad abecede A.
, zatim riječ xy(rezultat pripisivanja riječi na na kraju riječi x) Zove se ulančavanje
(kvačilo
,
raditi
) riječi x I na.
(n uzmimo već jednom x). Stavimo 
.
oblik mnogo podriječi
Jezik L, što je označeno sa Subw( L).
- ova riječ ima podriječi ab,
aba,
ba i tako dalje.
je jezik iznad abecede ( a,
b). Ovaj jezik je beskrajan, sadrži riječi b,
ba,
aba,
baa,
abaa,
baaa,
aabaa,
abaaa itd.
, Gdje 
, nazvan komplementom jezika L u vezi s abecedom A. A ako je uvijek uključeno u A*, zatim jezik 
može ali ne mora sadržavati . U potonjem slučaju 
.
,
. Tada se zove jezik ulančavanje
(kvačilo
,
raditi
) Jezici
I
. pri čemu 
,
(n puta) ako n>0.
,
,To .
.
(ova se operacija također naziva Kleene zvjezdica
). Jezik 
nazvao pozitivna iteracija
Jezik L.
.
. Zatim jezik 
nazvao apel
Jezik L.
oblik mnogo prefiksa
ovog jezika: Pref( L)
. Slično Suf( L)
-m
nož sufiksa
Jezik 
.
zadovoljava uvjet za sve riječi 
I 
, zatim preslikavanje f nazvao homomorfizam
.
.
– homomorfizam, 
I 
, zatim kroz f(L 1) naveden je jezik 
, i kroz 
jezik je naznačen 
, i sam zaslon 
nazvao inverzija homomorfizma
.
I 
. Ako 
, To 
.
I 
. Zatim 
I 
.