Standardna jezikovna definicija je teorija avtomatov. Redni jeziki in končni stroji

Regularne slovnice, končni avtomati in regularni nizi (in njihovi regularni izrazi) so trije različni načini definiranja regularnih jezikov.

Izjava

Jezik je PM, če in samo, če je podan z levo-linearno (desno-linearno) slovnico. Jezik je mogoče določiti z levo-linearno (desno-linearno) slovnico, če in samo če je običajen niz.

Jezik je PM, če in samo, če je določen z uporabo končnega stroja. Državni stroj prepozna jezik, če in samo če je PM.

Vse tri metode so enakovredne. Obstajajo algoritmi, ki omogočajo, da jezik, določen z eno od navedenih metod, sestavi drugo metodo, ki definira isti jezik. Natančen opis ti algoritmi so v literaturi (glej seznam).

Na primer, da bi našli regularni izraz za jezik, ki ga daje desno-linearna slovnica, je treba zgraditi in rešiti sistem enačb z rednimi koeficienti.

V teoriji programskih jezikov ima najpomembnejšo vlogo enakovrednost CA in običajnih slovnic, saj se takšne slovnice uporabljajo za definiranje leksikalnih struktur programskih jezikov. Ko izdelamo avtomat na podlagi znane slovnice, dobimo prepoznalnik za dani jezik. Tako je mogoče rešiti problem razčlenjevanja leksikalnih struktur jezika.

Če želite zgraditi CA na podlagi znane redne slovnice, ga je treba reducirati na avtomatsko obliko. Nabor stanj avtomata bo ustrezal množici neterminalnih simbolov slovnice. 2.3.2 Lastnosti običajnih jezikov

Množica se imenuje zaprta glede na neko operacijo, če kot rezultat izvajanja te operacije na katerem koli njenem elementu dobimo nov element, ki pripada isti množici.

Redni nizi so zaprti glede na operacije preseka, združitve, dopolnjevanja, ponovitve, povezovanja, spreminjanja imen simbolov in zamenjave nizov namesto simbolov.

Za običajne jezike so rešljivi številni problemi, ki niso rešljivi za druge vrste jezikov. Naslednje težave so na primer rešljive ne glede na to, na kakšen način je določen jezik:

Problem enakovrednosti: podana sta dva redna jezika L 1 (V) in L 2 (V). Treba je ugotoviti, ali so enakovredni.

Problem pripadnosti verige jeziku. Glede na običajni jezik L (V), niz simbolov V *. Želite preveriti, ali ta niz pripada jeziku.

Problem praznine jezika. Podan je običajen jezik L (V). Treba je preveriti, ali je ta jezik prazen, t.j. najti vsaj eno verigo, L (V).

Včasih je treba dokazati, da je določen jezik reden. Če je mogoče ta jezik nastaviti na enega od obravnavanih načinov, potem je običajen. Če pa takšne metode ni mogoče najti, ni znano, ali jezik ni običajen, ali pa preprosto ni bilo mogoče najti načina, kako ga definirati. Obstaja preprosta metoda za preverjanje, ali je zadevni jezik običajen. Dokazano je, da če za neki jezik t.i. lema rasti, potem je pravilna. Če ta lema ne uspe, potem jezik ni reden.

Lema o preraščanju je oblikovana na naslednji način. Če dobite navaden jezik in dovolj dolg niz simbolov, ki pripadajo temu jeziku, potem lahko v njem najdete neprazen podniz, ki ga lahko ponovite kolikorkrat želite in vsi tako pridobljeni nizi bodo tudi spadajo v obravnavani običajni jezik.

Formalno je lema zapisana takole. Če je jezik L podan, potem je konstanta p> 0, tako da če sta L in p, potem lahko verigo zapišemo v obliki, kjer je 0

Primer. Razmislite o jeziku L = (a n b n n > 0). Dokažimo, da ni redno uporabljati leme o širjenju jezikov.

Naj je ta jezik pravilen, potem mora zanj veljati lema o preraščanju. Vzemimo nekaj verige tega jezika = a n b n in jo zapišemo v obliki. Če je a + ali b +, potem niz i ne pripada jeziku za noben i, kar je v nasprotju s pogoji leme. Če je a + b +, potem tudi niz 2 ne pripada jeziku L. Dobili smo protislovje, zato jezik ni reden.

Redni kompletiin regularne izraze

Redni kompleti

V tem razdelku bomo obravnavali razred množic verig nad končnim besednjakom, ki jih je zelo enostavno opisati z nekakšnimi formulami. Ti sklopi se imenujejo redni.

Opredelitev 1.Naj bo V 1 in V 2 - veliko verig. Določimo tri operacijena teh kompletih.

Zveza: V 1 V 2 = ( |   V 1) ali   V 2.

Povezovanje (izdelek, lepljenje): Vl V2 = ( |   V 1,   V 2) Znak operacije povezovanja je običajno izpuščen.

Primer: V, = (abc, ba), V 2 = (b, cb). V1V2 = (abcb, abccb, bab, bacb).

Z V n označimo produkt n množic V: V n = VV ... V, V ° = () (tukaj -prazna veriga).

Primer: V 1 = (abc, ba), V 1 2 = (abcabc, abcba, baba, baabc).

3. Iteracija: V * = V 0 V 1 V 2  ... =   = 0 ∞ V n.

Primer: V = (a, bc), V * = (, a, bc, aa, abc, bcbc, bca, aaa, aabc, ...).

Opredelitev 4.13.Razred rednih množic nad končnim besednjakom V odedeje takole:

zveza ST;

povezovanje ST;

ponovitev S * in T *.

5. Če množice ni mogoče sestaviti s končnim številom aplikacij pravil 1-4, potem je nepravilna.

Primeri rednih nizov: (ab, ba) * (aa); (b) ((c)  (d, ab) *). Primeri nepravilnih množic: (a n b n | n> 0); ( | v verigi  je število pojavljanj simbolov a in b enako).

Regularni izrazi

Dobra stvar pri regularnih nizih je, da jih lahko zelo preprosto opišemo s formulami, ki jih bomo imenovali regularni izrazi.

Opredelitev 2.Razred regularnega izraza nad ciljnim slovarjem V odedeje takole:

njihova vsota R1 + R2;

njihov produkt R1R2;

njuna ponovitev je R1 * in R2 *.

4. Če izraz ni sestavljen s končnim številom aplikacij pravil 1-3, potem ni reden.

Simbol za delo je mogoče izpustiti. Za zmanjšanje števila oklepajev, kot v kateri koli algebri, se uporabljajo prioritete operacij: ponovitev ima najvišjo prioriteto; manj prednostno delo; dodajanje ima najnižjo prioriteto.

Primeri regularnih izrazov: ab + ba *; (aa) * b + (c + dab) *.

Očitno so si regularni nabori in regularni izrazi precej blizu. Vendar predstavljajo različne entitete: redni niz je niz verig (v splošnem primeru neskončen) in regex jeformula, ki shematično prikazuje, kako je bil ustrezen redni niz sestavljen z uporabo zgornjih operacij(in ta formula je končna).

Naj bo R ^ regularna množica, ki ustreza regularnemu izrazu R. Potem:

Tako je regularni izraz končna formula, ki definira neskončno število nizov, to je jezik.

Oglejmo si primere regularnih izrazov in ustreznih jezikov.

Vsakdanje izražanje	Ustrezen jezik
	Vsi nizi, ki se začnejo z b, ki mu sledi poljubno število znakov a
	Vsi nizi iz a in b, ki vsebujejo natanko dve pojavitvi b
	Vsi nizi a in b, v katerih se znaka b pojavljata samo v parih
(a + b) * (aa + bb) (a + b) *	Vse verige iz a in b, ki vsebujejo vsaj en par sosednjih a ali b
(0+1)*11001(0+1)*	Vse verige 0 in 1, ki vsebujejo podverigo 11001
	Vsi nizi a in b, ki se začnejo z a in končajo z b

Očitno je nabor nizov reden, če in samo, če ga je mogoče predstaviti z regularnim izrazom. Vendar pa je lahko isti niz nizov predstavljen z različnimi regularnimi izrazi, na primer niz nizov, ki so sestavljeni iz znakov a in vsebujejo vsaj dva a, je lahko predstavljen z naslednjimi izrazi: aa * a; a * aaa *; aaa *; a * aa * aa * itd.

Opredelitev 3.Dva regularna izraza R1 in R2 se imenujejo enakovredni (označeni Rl = R2) če in samo čeR1 ^ = R2 ^ .

Tako je aa * a = a * aaa * = aaa * = a * aa * aa *. Postavlja se vprašanje, kako določiti enakovrednost dveh regularnih izrazov.

Izrek1 . Za kateri koli regex R, S in T pošteno:

Te relacije je mogoče dokazati s preverjanjem enakosti ustreznih nizov. Uporabljajo se lahko za poenostavitev regularnih izrazov. Na primer: b (b + aa * b) = b (b + aa * b) = b ( + aa *) b = ba * b. Zato b (b + aa * b) = ba * b, kar ni očitno.

Kleenejev izrek

Regularni izrazi so končne formule, ki definirajo regularne jezike. Toda končni stroji imajo podobno lastnost – definirajo tudi jezike. Postavlja se vprašanje: kako so jezikovni razredi opredeljeni z državnimi stroji in regularnimi izrazi med seboj povezani? Označujemo In veliko samodejnih jezikov, R je niz običajnih jezikov. Stephen Kleene, ameriški matematik, je dokazal naslednji izrek.

Izrek2 . (Kleenejev izrek.) Razredi rednih množic in avtomatskih jezikov sovpadajo, tj. A = R .

Z drugimi besedami, vsak jezik avtomata je mogoče določiti s formulo (regularni izraz) in vsak regularni niz je mogoče prepoznati s končnim avtomatom. Ta izrek bomo konstruktivno dokazali v dveh korakih. V prvem koraku bomo dokazali, da je kateri koli avtomatski jezik regularna množica (ali, kar je enako, lahko za kateri koli končni avtomat sestavimo regularni izraz, ki definira jezik, ki ga ta avtomat prepozna). V drugem koraku dokažemo, da je vsaka regularna množica avtomatski jezik (ali, kar je enako, za kateri koli regularni izraz lahko sestavimo končni avtomat, ki dovoljuje natančno verige ustrezne regularne množice).

Predstavimo model prehodnega grafa kot posplošitev modela državnega stroja. V prehodnem grafu sta eno začetno in poljubno število končnih vozlišč, usmerjeni robovi pa so v nasprotju s državnim strojem označeni ne s simboli, ampak z regularnimi izrazi. Prehodni graf dopušča verigo a if a pripada množici verig, opisanih z zmnožkom regularnih izrazov R 1 R 2 ... R n, ki označujejo pot od začetnega vrha do enega od končnih vozlišč. Nabor verig, ki jih dovoljuje prehodni graf, tvori jezik, ki ga sprejema.

riž. 1. Graf prehodov

Na sl. 1 prikazuje prehodni graf, ki omogoča na primer verigo abbca, saj je pot s-> r-> p-> s-> r-> q, ki vodi do končnega stanja q, označena z verigo regularnih izrazov  • a • b *   · c * a. Končni avtomat je poseben primer prehodnega grafa, zato so vsi jeziki, ki jih dovoljujejo avtomati, dovoljeni tudi s prehodnimi grafi.

3. izrek.Vsak avtomatski jezik je običajen nabor, A  R.

Dokaz. Prehodni graf z enim začetnim in enim končnim ogliščem, v katerem je edini rob od začetnega do končnega oglišča označen z regularnim izrazom R, dopušča jezik R ^ (slika 1).

riž. 2. Prehodni graf, ki dopušča običajni jezik FT

Dokažimo zdaj, da je vsak avtomatski jezik redni niz redukcij katerega koli grafa prehodov, ne da bi spremenili sprejeti jezik v enakovredno obliko (slika 2).

Vsak končni avtomat in kateri koli prehodni graf je vedno mogoče predstaviti v normalizirani obliki, v kateri je samo eno začetno točko samo z izhodnimi robovi in ​​samo eno končno vozlišče samo z vhodnimi robovi (slika 3).

riž. 3. Prehodni graf z enim začetnim in enim končnim vrhom

S prehodnim grafom, ki je predstavljen v normalizirani obliki, je mogoče izvesti dve operaciji redukcije - redukcijo roba in redukcijo vrhov - ob ohranjanju jezika, ki ga dovoljuje ta prehodni graf:

a) zmanjšanje rebra:

B ) redukcija oglišča (zamenjava se izvede za vsako pot, ki poteka skozi oglišče p, z njegovo kasnejšo zavrženjem kot nedosegljivo stanje):

Očitno je, da vsaka operacija redukcije ne spremeni jezika, ki ga prepozna prehodni graf, ampak zmanjša bodisi število robov ali število vozlišč, sčasoma pa bodo redukcije prehodni graf pripeljale do oblike, prikazane na sliki. 2. Izrek je dokazan: vsak avtomatski jezik je redna množica.

Primer

Naj bo podan končni stroj A:

Zgradimo enakovredni prehodni graf v normalizirani obliki.

Zmanjšanje oglišča 3:

Redukcija lokov in uporaba pravila R = R:

Zmanjšanje oglišča 2:

Zmanjšanje loka in vrha 1:

Tako je jezik, ki ga prepozna avtomat A, določen z regularnim izrazom: R A = b + (a + bb) (b + ab) * a.

Dokažimo Kleenejev izrek v drugi smeri.

2. izrek.Vsak običajen niz je avtomatski jezik: R  A.

Dokaz. Pokažimo, da je za vsak regularni izraz R mogoče konstruirati končni avtomat A r (morda nedeterminističen), ki prepozna jezik, ki ga poda R. Takšne avtomate definirajmo rekurzivno.

(začetno in končno stanje A sta združena).

Primer(nadaljevanje)

Laboratorijsko delo št. 3

Razvoj leksikalnega analizatorja je dovolj enostaven, če se uporablja teorija rednih jezikov in končnih avtomatov. V okviru te teorije se razredi iste vrste žetonov obravnavajo kot formalni jeziki (jezik identifikatorjev, jezik konstant itd.), katerih nabor stavkov je opisan z ustrezno generativno slovnico. Poleg tega so ti jeziki tako preprosti, da jih generira najpreprostejša slovnica - navadna slovnica.

Opredelitev 1... generativna slovnica G = , katerih pravila imajo obliko: A :: = aB ali C :: = b, kjer je A, B, C Є N; a, b Є Т se imenuje redni (avtomatski).

Jezik L (G), ki ga generira avtomatska slovnica, se imenuje avtomatski (navadni) jezik ali jezik s končnim številom stanj.

Primer 1... Razred identifikatorjev, če je identifikator zaporedje črk in številk, prvi znak identifikatorja pa je lahko samo črka, opisuje naslednja generativna redna slovnica G = , pri čemer

N = (I, K), T = (b, q), S = (I),

P = (1.I :: = b

Tukaj so b, c posplošeni terminalski simboli za črke oziroma številke.

Postopek generiranja identifikatorja "bbtsbts" je opisan z naslednjim zaporedjem zamenjav

I => bK => bbK => bbtsK => bbtsbK => bbtsbts

Vendar glavna naloga LA ni generiranje leksikalnih enot, temveč njihovo prepoznavanje. Matematični model običajnega procesa prepoznavanja jezika je računalniška naprava, imenovana končni avtomat (CA). Izraz "končno" poudarja, da ima računalniška naprava fiksno in končno količino pomnilnika in obdeluje zaporedje vhodnih znakov, ki pripadajo nekemu končnemu nizu. Obstaja Različne vrste CA, če je izhodna funkcija CA (rezultat dela) le pokazatelj, ali je vhodno zaporedje simbolov dovoljeno ali ne, se taka CA imenuje končni prepoznavalec.

Definicija 2. Naslednjih pet se imenuje končni avtomat:

A = , kjer je V = (a 1, a 2,…, a m) - vhodna abeceda (končna množica simbolov);

Q = (q 0, q 1,…, q n -1) - abeceda stanj (končna množica simbolov);

δ: Q × V → Q je prehodna funkcija;

q 0 Є Q začetno stanje končnega avtomata;

F Є Q - množica končnih stanj.

Shema delovanja SC.

Obstaja neskončen trak, razdeljen na celice, od katerih lahko vsaka vsebuje en znak iz V. Trak vsebuje verigo α Є V *. Celice levo in desno od verige so prazne. Obstaja končna krmilna naprava (CU) z bralno glavo, ki lahko zaporedno bere znake s traku, ki se premika po traku od leve proti desni. V tem primeru je lahko CU v katerem koli stanju od Q. CU vedno začne svoje delo v začetnem stanju q 0 in se konča v enem od končnih stanj F. Vsakič, ko preide v novo celico na traku, CU preide v novo stanje v skladu s funkcijo δ.

Prehodno funkcijo vesoljskega plovila lahko predstavimo na naslednje načine:

· Nabor ekip;

· diagram stanja;

· Prehodna miza.

Ukaz državnega stroja je zapisan takole:

(q i, a j) → q k, kjer je q i, q k Є Q; a j Є V.

Ta ukaz pomeni, da je državni stroj v stanju q i, prebere simbol a j s traku in preide v stanje q k.

Grafično je ukaz predstavljen v obliki loka grafa, ki poteka od vrha q i do vrha q k in označen s simbolom a j vhodne abecede:

Grafični prikaz celotnega preslikave δ se imenuje diagram državnega stroja.

Če se vesoljsko plovilo znajde v situaciji (q i, a j), ki ni leva stran nobenega ukaza, se ustavi. Če UU prešteje vse simbole niza α, posnete na traku, in hkrati preide v končno stanje q r Є F, potem pravimo, da verigo α sprejme končni avtomat.

Prehodna tabela CA je sestavljena na naslednji način: stolpci matrike ustrezajo simbolom iz vhodne abecede, vrstice ustrezajo simbolom iz abecede stanj, elementi matrike pa stanjem, v katera prehaja CA. za dano kombinacijo vhodnega simbola in simbola stanja.

Naj bo redna slovnica G = , katerih pravila so v obliki: А i :: = a j A k ali А i :: = a j, kjer je A i, A k Є N in a j Є T.

Potem je končni avtomat A = ki dopušča isti jezik, kot ga generira običajna slovnica G, je zgrajena na naslednji način:

2) Q = N U (Z), Z N in Z T, Z - končno stanje vesoljskega plovila;

5) Preslikava δ je sestavljena v obliki:

· Vsako pravilo substitucije v slovnici G oblike А i :: = a j A k je povezano z ukazom (А i, a j) → A k;

· Vsako pravilo zamenjave v obliki А i :: = a j je povezano z ukazom (А i, a j) → Z;

Primer 2. Konstruirajte CA za slovnico iz primera 1. Imamo A = , kje

1) V = T = (b, c)

2) Q = N U (Z) = (I, R, Z)

3) q 0 = (S) = (I)

5) δ: a) kot niz ukazov:

b) v obliki diagrama stanja

Razlikovati med determinističnimi in nedeterminističnimi končnimi avtomati. Vesoljsko plovilo se imenuje nedeterministična CA (NCA), če v diagramu njegovih stanj iz enega vrha izhaja več lokov z enakimi oznakami. Na primer, vesoljsko plovilo iz primera 2 je vesoljsko plovilo.

Za praktične namene je potrebno, da končni prepoznalnik sam določi trenutek konca vhodnega zaporedja znakov z izdajo sporočila o pravilnosti ali napačnosti vnosnega niza. Za te namene se šteje, da je vhodna veriga na desni omejena s končnim markerjem ├, interpretirana stanja pa so vnesena v diagram stanja SC:

Z - "priznaj vhodno verigo";

О - "napaka je bila shranjena v vhodni verigi";

E - "zavrni vnosno stopnico."

Stanji Z in E sta končni, CA pa ju vnese ob branju končne oznake ├ po obdelavi pravilne ali napačne vhodne verige. Stanje O je vmesno, vanj CA preide iz katerega koli dopustnega stanja CA, ko je v vhodni verigi zaznana napaka in ostane v njem, dokler ne prispe končni marker ├, po katerem se izvede prehod v stanje E - "zavrni vhodno verigo«.

V tem poglavju začnemo orisati elemente teorije. formalnih jezikih.

Ko rečemo "formalni jezik", mislimo, da se tukaj predstavljeni rezultati uporabljajo predvsem pri opisu umetnih jezikov, ki so jih izumili ljudje za posebne namene, na primer programskih jezikov. Vendar ni nepremostljive ovire med posebej izumljenimi umetnimi (formalnimi) jeziki in spontano nastajajočimi in razvijajočimi se naravnimi jeziki. Izkazalo se je, da so za naravne jezike značilna zapletena slovnična pravila, tj. so precej togo formalizirani in tudi najbolj "znanstveno razvit" programski jezik vsebuje "temne kraje", katerih nedvoumno razumevanje je problem.

Pri učenju jezikov je treba upoštevati tri glavne vidike.

Prvi je jezikovna sintaksa ... Jezik je niz "besed", kjer je "beseda" določeno končno zaporedje "črk" - simbolov neke vnaprej določene abecede. Izraza "črka" in "beseda" je mogoče razumeti na različne načine (matematična definicija teh izrazov bo podana spodaj). Torej so "črke" lahko dejansko črke abecede nekega naravnega ali formalnega jezika, na primer ruskega jezika ali programskega jezika Pascal. Potem bodo "besede" končna zaporedja "črk": krokodil "," celo število". Takšne besede se imenujejo" leksemi. "A" črka "je lahko" beseda "(" leksem ") kot celota. potem ne bo vsaka njihova zaporedja "beseda", tj. Eleksema "danega jezik, ampak le takšno zaporedje, ki upošteva določena pravila. Beseda "krykadil" ni leksem ruskega jezika, beseda "iff" pa ni leksem v Pascalu. Stavek "Ljubim te" ni pravilen stavek ruskega jezika, tako kot zapis "x: = = t" ni pravilno napisan operator dodelitve v Pascalu. Sintaksa * jezika je sistem pravil, po katerih je mogoče sestaviti »pravilna« zaporedja »črk«. Za vsako besedo v jeziku je značilna določena struktura, ki je značilna za ta jezik. Nato je treba na eni strani razviti mehanizme za naštevanje oziroma generiranje besed z dano strukturo, na drugi strani pa mehanizme za preverjanje dana beseda pripada danemu jeziku. Prvič, prav te mehanizme preučuje klasična teorija formalnih jezikov.

Drugi vidik je semantika jezika ... Semantika ** predpostavlja primerjavo besed v jeziku določenega »pomena«, vrednotenja. »Pri pisanju matematične formule moramo na primer upoštevati določene pravila sintakse(postavitev oklepajev, črkovanje simbolov, vrstni red simbolov itd.), a poleg tega ima formula zelo določen pomen, nekaj pomeni.

Jezik je sredstvo komunikacije, prenosa informacij. Če želimo biti razumljeni, moramo ne le skladenjski pravilno, ob upoštevanju pravilnega vrstnega reda črk v besedi in besed v stavku, graditi svoj govor, ampak tudi skrbeti za njegov pomen, za ideje, ki jih izražamo v govoru. Matematične teorije"sense" se je pojavil relativno nedavno, poleg naslednjega poglavja pa bomo zelo na kratko obravnavali nekatere pristope k matematičnemu opisu semantike programskih jezikov.

* Beseda "sintaksa" izvira iz starogrškega "syn" - "skupaj" in "taxis" - "red, red". Tako lahko sintakso razumemo kot "sestavljanje".

** Iz starogrških besed "sema" - "znak, znak" in "semanticos" - "označevanje".

Končno, tretji vidik - pragmatika jezika ... Pragmatika je povezana s cilji, ki si jih zastavi materni govorec: na primer, oseba govori, ima cilje, ki niso povezani s sintakso, ne s semantiko jezika, v katerem govori ali piše, ampak npr. prejeti določeno vsoto denarja. Pragmatika je že prej socialno-filozofska disciplina, ki vpliva na ciljno usmerjeno dejavnost posameznika. Niti najmanj se je ne bomo dotaknili.

V tem poglavju bomo najprej obravnavali osnovne pojme matematične teorije formalnih jezikov, med katerimi je najpomembnejši pojem generativne slovnice, nato pa tako imenovani regularni jeziki. Teorija regularnih jezikov skupaj s teorijo končnih avtomatov predstavlja temelj celotne teorije formalnih jezikov.

• Abeceda, beseda, jezik

• Generativne slovnice

  Kot smo že omenili, klasična teorija formalnih jezikov preučuje predvsem skladnjo jezika. Uvaja matematični sintaksni model, ki opisuje mehanizme za generiranje in prepoznavanje "dobro oblikovanih" nizov. V tem razdelku si bomo ogledali prvega od teh mehanizmov.

poznamo operacije združevanja jezikov. Definirajmo operacije združevanja in iteracije (včasih imenovane Kleenejevo zapiranje).

Naj sta L 1 in L 2 jezika v abecedi

Potem, tj. povezovanje jezikov sestoji iz povezovanja vseh besed prvega jezika z vsemi besedami drugega jezika. Še posebej, če, potem in če, potem.

Naj uvedemo zapis "stopinj" jezika L:

Tako L i vsebuje vse besede, ki jih je mogoče razdeliti na i zaporednih besed iz L.

Iteracijo (L) * jezika L tvorijo vse besede, ki jih je mogoče razdeliti na več zaporednih besed iz L:

Lahko ga predstavimo s stopnjami:

Pogosto je priročno razmisliti o "okrnjeni" iteraciji jezika, ki ne vsebuje prazne besede, če ni v jeziku: ... To ni nova operacija, ampak le priročna okrajšava za izraz.

Upoštevajte tudi, da če upoštevamo abecedo kot končni jezik, sestavljen iz enočrkovnih besed, potem prej uvedena oznaka za množico vseh besed, vključno s prazno, v abecedi ustreza definiciji iteracije tega jezika.

Naslednja tabela ponuja formalno induktivno definicijo regularnih izrazov nad abecedo in jeziki, ki jih predstavljajo.

Izraz r	Jezik L r
	L a = (a)
Naj bosta r 1 in r 2	L r1 in L r2 sta reprezentativna
regularnih izrazov.	teh jezikov.
Nato naslednji izrazi
so redni	in predstavljajo jezike:
r = (r 1 + r 2)
r = (r 1 krog 2)
r = (r 1) *	L r = L r1 *

Pri snemanju regularnih izrazov izpustili bomo predznak za povezovanje in predpostavili, da ima operacija * višjo prioriteto kot povezovanje in +, povezovanje pa ima višjo prioriteto kot +. To bo izpustilo številne oklepaje. na primer lahko zapišemo kot 10 (1 * + 0).

Opredelitev 5.1... dva regularnih izrazov r in p naj bi bila enakovredna, če jezika, ki ju predstavljata, sovpadata, t.j. L r = L p. V tem primeru zapišemo r = p.

Preprosto je preveriti npr lastnosti rednega operacije:

• r + p = p + r (komutativnost unije),
• (r + p) + q = r + (p + q) (asociativnost asociativnosti),
• (r p) q = r (p q) (konkatenacijsko asociativnost),
• (r *) * = r * (idempotenca iteracije),
• (r + p) q = rq + pq(distribucija).

Primer 5.1... Dokažimo na primer ne tako očitno enakost: (r + p) * = (r * p *) *.

Naj bo L 1 jezik, ki ga predstavlja njegova leva stran, L 2 pa desna. Prazna beseda pripada obema jezikoma. Če je neprazna beseda, je po definiciji iteracije predstavljena kot povezovanje podbesed, ki pripadajo jeziku. Toda ta jezik je podmnožica jezika L "= L r * L p * (zakaj?). Zato ... Nasprotno, če je beseda, jo lahko predstavimo kot združitev podbesed, ki pripadajo jeziku L. "Vsako od takih podbesed v je mogoče predstaviti v obliki v = v 1 1 ... v k 1 v 1 2 ... v l 2, kjer je za vse i = 1, ..., k podbeseda in za vse j = 1, ..., l podbeseda (možno je, da je k ali l enak 0). Toda to pomeni, da je w povezava podbesed, od katerih vsaka pripada in zato.