Vanlige språk og finite state-maskiner. Regulært språk Regulære språk og finite state-maskiner

Vanlige settog regulære uttrykk

Vanlige sett

I denne delen vil vi vurdere en klasse med sett med kjeder over en begrenset ordbok, som er veldig enkle å beskrive med formler av noe slag. Disse settene kalles vanlige.

Definisjon 1.La V 1 Og V 2 - mange kjeder. La oss definere tre operasjonerpå disse settene.

Union: V 1 V 2 =(|   V 1 ) eller   V 2 .

Sammenknytting (produkt, liming): Vl V2 = (|  V 1 ,  V 2 ) Tegnet for sammenkoblingsoperasjonen er vanligvis utelatt.

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

La oss betegne med V n produktet av n sett V:V n =VV...V,V° =() (her er  en tom kjede).

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

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

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

Definisjon 4.13.Klasse med vanlige sett over en begrenset ordbok V defineregår slik:

fagforeningen ST;

ST-sammenkobling;

iterasjon S* og T*.

5. Hvis et sett ikke kan konstrueres av et begrenset antall anvendelser av regel 1-4, så er det uregelmessig.

Eksempler på vanlige sett: (ab, ba)* (aa); (b)((c)(d, ab)*). Eksempler på uregelmessige sett: (a n b n | n > 0); ( | i kjede  er antall forekomster av symbolene a og b sammenfallende).

Vanlig uttrykk

Regulære sett er bra fordi de kan beskrives veldig enkelt med formler, som vi vil kalle regulære uttrykk.

Definisjon 2.Regelmessig uttrykk klasse over finitt ordbok V defineregår slik:

deres sum R1+R2;

deres produkt R1R2;

deres iterasjon R1* og R2*.

4. Hvis et uttrykk ikke er konstruert ved å bruke regel 1-3 endelig, så er det ikke regulært.

Arbeidssymbolet kan utelates. For å redusere antall parenteser, som i enhver algebra, brukes operasjonsprioriteter: iterasjon har høyeste prioritet; arbeidet har mindre prioritet; tillegg har lavest prioritet.

Eksempler på regulære uttrykk: ab + bа*; (aa)*b + (c + dab)*.

Det er klart at vanlige sett og regulære uttrykk er veldig nære. Men de representerer forskjellige enheter: et vanlig sett er et sett med kjeder (i det generelle tilfellet uendelig), og regulært uttrykk eren formel som skjematisk viser hvordan det tilsvarende vanlige settet ble konstruert ved bruk av operasjonene som er oppført ovenfor(og denne formelen er endelig).

La R^ være et regulært sett som tilsvarer det regulære uttrykket R. Så:

Dermed er et regulært uttrykk en endelig formel som definerer et uendelig antall kjeder, det vil si et språk.

La oss se på eksempler på regulære uttrykk og deres tilsvarende språk.

Vanlig uttrykk	Tilsvarende språk
	Alle strenger som begynner med b etterfulgt av et vilkårlig antall tegn a
	Alle strenger av a og b som inneholder nøyaktig to forekomster av b
	Alle kjeder av a og b der symbolene b bare vises i par
(a+b)*(aa+bb)(a+b)*	Alle kjeder av a og b som inneholder minst ett par av tilstøtende a eller b
(0+1)*11001(0+1)*	Alle kjeder av 0 og 1 inneholder underkjede 11001
	Alle strenger av a og b, som starter med a og slutter med b

Selvfølgelig er et sett med strenger regulært hvis og bare hvis det kan representeres av et regulært uttrykk. Imidlertid kan det samme settet med kjeder representeres av forskjellige regulære uttrykk, for eksempel kan et sett med kjeder som består av symbolene a og inneholder minst to a representeres av uttrykkene: aa*a; a*aaa*; aaa*; a*aa*aa* osv.

Definisjon 3.To regulære uttrykk R1 Og R2 kalles ekvivalente (betegnet Rl = R2) da og bare nårR1 ^ = R2 ^ .

Dermed er aa*a = a*aaa* = aaa* = a*aa*aa*. Spørsmålet oppstår hvordan man bestemmer ekvivalensen til to regulære uttrykk.

Teorem1 . For alle regulære uttrykk R, S Og T rettferdig:

Disse relasjonene kan bevises ved å kontrollere likheten til de tilsvarende settene med kjeder. De kan brukes til å forenkle regulære uttrykk. For eksempel: b (b + aa*b) = b (b + aa*b) = b ( + aa*) b = ba*b. Derav b (b + aa*b) = ba*b, som ikke er åpenbart.

Kleenes teorem

Regulære uttrykk er de endelige formlene som definerer regulære språk. Men endelige tilstandsmaskiner har også en lignende egenskap - de definerer også språk. Spørsmålet oppstår: hvordan forholder klassene av språk definert av endelige tilstandsmaskiner og regulære uttrykk seg til hverandre? La oss betegne Og mange automatiske språk, R er et sett med vanlige språk. Stephen Kleene, en amerikansk matematiker, beviste følgende teorem.

Teorem2 . (Kleenes teorem.) Klassene av regulære sett og automatspråk faller sammen, dvs. A = R .

Med andre ord kan hvert automatspråk spesifiseres av en formel (regulært uttrykk) og hvert regulære sett kan gjenkjennes av en endelig automat. Vi vil bevise dette teoremet konstruktivt, i to trinn. I det første trinnet vil vi bevise at et hvilket som helst automatspråk er et regulært sett (eller, hva er det samme, for enhver finitt automat kan vi konstruere et regulært uttrykk som spesifiserer språket som gjenkjennes av denne automaten). I det andre trinnet vil vi bevise at ethvert regulært sett er et automatspråk (eller, hva som er det samme, fra et hvilket som helst regulært uttrykk kan man konstruere en endelig automat som tillater nøyaktig kjedene til det tilsvarende regulære settet).

La oss introdusere overgangsgrafmodellen som en generalisering av den endelige automatmodellen. Overgangsgrafen har ett initialt og et vilkårlig antall siste hjørner, og rettede kanter er markert, i motsetning til en endelig automat, ikke med symboler, men med regulære uttrykk. Overgangsgrafen innrømmer en kjede et if EN tilhører et sett med kjeder, beskrevet av produktet av regulære uttrykk R 1 R 2 ...R n , som markerer banen fra startpunktet til et av sluttpunktene. Settet med kjeder tillatt av overgangsgrafen danner språket som er tillatt av det.

Ris. 1. Overgangsgraf

I fig. Figur 1 viser en overgangsgraf som tillater for eksempel en kjede-abbca, siden banen s->r->p->s->r->q, som fører til slutttilstanden q, er merket med en kjede av regulære uttrykk ab* c*a. En endelig tilstandsmaskin er et spesialtilfelle av en overgangsgraf, og derfor støttes alle språk som er akseptert av tilstandsmaskiner også av overgangsgrafer.

Teorem 3.Hvert automatspråk er et vanlig sett, A  R.

Bevis. En overgangsgraf med ett initialt og ett siste toppunkt, der den eneste kanten fra initial til siste toppunkt er merket med et regulært uttrykk R, tillater språket R^ (fig. 1).

Ris. 2. Overgangsgraf som innrømmer vanlig språk FT

La oss nå bevise at hvert automatspråk er et vanlig sett ved å redusere enhver overgangsgraf uten å endre språket det tillater til en ekvivalent form (fig. 2).

Enhver endelig automat og en hvilken som helst overgangsgraf kan alltid representeres i en normalisert form, der det kun er ett innledende toppunkt med bare utgående kanter og bare ett endelig toppunkt med bare innkommende kanter (fig. 3).

Ris. 3. Overgangsgraf med ett innledende og ett siste toppunkt

Med en overgangsgraf presentert i normalisert form, kan to reduksjonsoperasjoner utføres - kantreduksjon og toppunktreduksjon - samtidig som språket tillatt av denne overgangsgrafen bevares:

a) ribbein reduksjon:

B ) toppunktreduksjon (erstatning utføres for hver bane som går gjennom toppunkt p, etterfulgt av at den forkastes som en uoppnåelig tilstand):

Det er klart at hver reduksjonsoperasjon ikke endrer språket som gjenkjennes av overgangsgrafen, men reduserer enten antall kanter eller antall toppunkter, og til slutt vil reduksjonene bringe overgangsgrafen til formen vist i fig. 2. Teoremet er bevist: hvert automatspråk er et vanlig sett.

Eksempel

La den endelige maskinen A gis:

Vi konstruerer en ekvivalent overgangsgraf i normalisert form.

Toppunktreduksjon 3:

Reduksjon av buer og anvendelse av regelen R = R:

Toppunktreduksjon 2:

Reduksjon av bue og toppunkt 1:

Dermed er språket som gjenkjennes av automat A gitt av det regulære uttrykket: RA = b+(a+bb)(b+ab)*a.

La oss bevise Kleenes teorem i den andre retningen.

Teorem 2.Hvert vanlig sett er et automatspråk: R EN.

Bevis. La oss vise at for hvert regulære uttrykk R kan det konstrueres en endelig automat A r (muligens ikke-deterministisk) som gjenkjenner språket spesifisert av R. Vi vil definere slike automater rekursivt.

(start- og slutttilstanden til A er kombinert).

Eksempel(fortsettelse)

Vanlige grammatikker, endelige automater og regulære sett (og de regulære uttrykkene som representerer dem) er tre forskjellige måter å spesifisere vanlige språk.

Uttalelse

Et språk er PM hvis og bare hvis det er spesifisert av en venstre-lineær (høyre-lineær) grammatikk. Et språk kan defineres av en venstre-lineær (høyre-lineær) grammatikk hvis og bare hvis det er et vanlig sett.

Et språk er PM hvis og bare hvis det er spesifisert av en endelig tilstandsmaskin. Et språk gjenkjennes av en statsmaskin hvis og bare hvis det er en PM.

Alle disse tre metodene er likeverdige. Det finnes algoritmer som gjør det mulig for et språk definert på en av disse måtene å konstruere en annen metode som definerer det samme språket. En detaljert beskrivelse av disse algoritmene er tilgjengelig i litteraturen (se liste).

For å finne et regulært uttrykk for et språk definert av en høyre-lineær grammatikk, er det for eksempel nødvendig å konstruere og løse et likningssystem med regulære koeffisienter.

I teorien om programmeringsspråk spilles den viktigste rollen av ekvivalensen av CA og vanlige grammatikker, siden slike grammatikker brukes til å definere leksikalske strukturer av programmeringsspråk. Etter å ha laget en automat basert på en kjent grammatikk, får vi en gjenkjenner for et gitt språk. På denne måten er det mulig å løse parseproblemet for leksikalske konstruksjoner av språket.

For å konstruere en CA basert på en kjent vanlig grammatikk, må den reduseres til en automatform. Settet med tilstander til automaten vil tilsvare settet med ikke-terminale symboler i grammatikken. 2.3.2 Egenskaper til vanlige språk

Et sett kalles lukket under en eller annen operasjon hvis, som et resultat av å utføre denne operasjonen på noen av elementene, oppnås et nytt element som tilhører samme sett.

Vanlige sett er stengt under operasjonene skjæring, forening, addisjon, iterasjon, sammenkobling, endring av symbolnavn og erstatning av strenger for symboler.

For vanlige språk kan mange problemer løses som er uløselige for andre typer språk. For eksempel kan følgende problemer løses uavhengig av hvordan språket er spesifisert:

Ekvivalensproblem: Gitt to vanlige språk L 1 (V) og L 2 (V). Det er nødvendig å avgjøre om de er likeverdige.

Problemet med kjedetilhørighet til språk. Gitt et vanlig språk L(V), en streng med symboler V * . Vi må sjekke om denne kjeden tilhører språket.

Problemet med språkets tomhet. Gitt et vanlig språk L(V). Det er nødvendig å sjekke om dette språket er tomt, dvs. finn minst én kjede, L(V).

Noen ganger er det nødvendig å bevise om et bestemt språk er vanlig. Hvis det er mulig å spesifisere dette språket på en av de vurderte måtene, er det vanlig. Men hvis en slik metode ikke kan finnes, er det ukjent om språket ikke er vanlig, eller om det rett og slett ikke var mulig å finne en måte å spesifisere det på. Det er en enkel metode for å sjekke om det aktuelle språket er vanlig. Det er bevist at hvis for et bestemt språk den såkalte utvidelseslemma, så er det vanlig. Hvis dette lemmaet ikke er oppfylt, er ikke språket regelmessig.

Vekstlemmaet er formulert som følger. Hvis gitt et vanlig språk og en tilstrekkelig lang kjede av symboler som tilhører dette språket, kan man i den finne en ikke-tom underkjede som kan gjentas så mange ganger som ønskelig, og alle kjeder oppnådd på denne måten vil også tilhøre det aktuelle vanlig språket.

Formelt er lemmaet skrevet som følger. Hvis et språk L er gitt, så er konstanten p>0 slik at hvis L og p, så kan kjeden skrives på formen hvor 0

Eksempel. Tenk på språket L=(a n b n n>0). La oss bevise at det ikke er vanlig å bruke lemmaet om spredning av språk.

La dette språket være regelmessig, så må ekspansjonslemmaet holde for det. La oss ta en kjede av dette språket = a n b n og skrive det i skjemaet. Hvis a + eller b + , så hører ikke strengen i til språket for noen i, noe som motsier vilkårene for lemmaet. Hvis a + b + , så hører heller ikke kjede 2 til språket L. Vi har fått en selvmotsigelse, derfor er ikke språket regulært.

Automateteori - Dette er en del av teorien kontrollsystemer, studere matematiske modeller av diskrete informasjonsomformere, kalt maskingevær. Fra et visst synspunkt er slike omformere både virkelige enheter (datamaskiner, automater, levende organismer, etc.) og abstrakte systemer (for eksempel et formelt system, aksiomatiske teorier osv.), som gjør det mulig å anvende teorien om automater innen forskjellig vitenskapelig og anvendt forskning. Teorien om automater er nærmest knyttet til matematisk logikk og teorien om algoritmer. Spesielt er løsbarheten til noen formelle kalkuler bevist ved hjelp av automatteori.

Et annet viktig studieemne i dette kurset er formelt språk 1 – et vilkårlig sett med ord i et eller annet alfabet. Betydningen av formelle språk for teoretisk informatikk skyldes det faktum at den enkleste og mest praktiske datamodellen som brukes i dataprogrammer er en endelig sekvens, hvor hvert element er hentet fra et forhåndsfiksert begrenset sett. Siden de formelle språkene som brukes i applikasjoner vanligvis er uendelige, er det nødvendig med en måte å beskrive det formelle språket på en begrenset måte. I dette kurset vil vi studere 3 klassiske virkemidler for denne beskrivelsen: maskingevær, vanlig uttrykk Og generative grammatikker.

Introduksjon

1. Grunnleggende begreper i teorien om formelle språk

Tenk på et ikke-tomt begrenset sett EN, bestående av tegn ( en 1 , …, en k). Vi ringer EN alfabet , og symbolene er bokstaver . Enhver endelig rekkefølge av bokstaver i dette alfabetet kalles i et ord (kjede eller linje ): w=en 1 en 2 …en n- ord ( en Jeg EN), |w| – ordlengde (antall bokstaver som utgjør ordet, hvor hvert tegn forekommer like mange ganger som det forekommer i w). Via | w| b angi antall forekomster av symbolet b per ord w.

Uendelig rekkefølge av alfabetbokstaver EN kalt superord , - et superord av et uendelig antall bokstaver EN. Tømme er et ord som ikke inneholder en eneste bokstav. Det er merket med . Tydeligvis ||=0.

- mange ord i alfabetet EN lengde n. Sett med alle ord i alfabetet EN(inkludert superord) er angitt EN*. Dette settet er tellbart fordi det er foreningen av et tellbart antall endelige sett
. Settet med alle ikke-tomme ord i alfabetet EN betegnet med EN+ . Hvis EN={en), Det EN*={en)* vil bli merket med EN*.

Enhver undergruppe
kalt tunge (formelt språk ) over alfabetet EN.

Hvis x Og y– språkets ord
, deretter ordet xy(resultat av å tilskrive ordet på på slutten av et ord X) er kalt sammenkobling (kløtsj , arbeid ) ord X Og på.
(n la oss ta det en gang X). La oss sette
.

De sier at ordet X – underord ord på, Hvis y=uxv for noen ord u Og v. Alle underord av ord i språket
form mange underord Språk L, som er betegnet med Subw( L).

Eksempler. 1. ba 3 =baaa,
- dette ordet har underord ab, aba, ba og så videre.

2. Sett ( en, abb) - språk (endelig) over alfabetet ( en, b}.

3. Masse
er et språk over alfabetet ( en, b). Dette språket er uendelig, det inneholder ord b, ba, aba, baa, abaa, baaa, aabaa, abaaa etc.

Siden hvert språk er et sett, kan vi vurdere operasjonene til forening, skjæringspunkt og forskjell mellom språk definert over det samme alfabetet. Ja, språk
, Hvor
, kalt komplementet til språket L angående alfabetet EN. Og hvis  alltid er inkludert i EN*, deretter språket
kan inneholde eller ikke inneholde . I sistnevnte tilfelle
.

La ,
. Da kalles språket sammenkobling (kløtsj , arbeid ) språk Og . Hvori
,
(n ganger), hvis n>0.

Eksempler. 1. Hvis
,
, Det.

2. Hvis L=(0, 01), så
.

Iterasjon Språk L kalt språk
(denne operasjonen kalles også Kleene stjerne ). Språk
kalt positiv iterasjon Språk L.

Eksempel. Hvis EN={en, b) Og L={aa, ab, ba, bb), Det
.

Ved klage eller i et speilbilde ord w ordet heter w R, der bokstavene i ordet w gå i motsatt rekkefølge. For eksempel hvis w=bac, Det

La
. Så tungen
kalt anke Språk L.

Vi vil kalle hver begynnelse av et ord prefiks , og hver ende av et ord - suffiks . For eksempel hvis y=xv, Det X– ordprefiks på(betegnelse – X[y), A v– ordsuffiks på(betegnelse – v]y). Åpenbart er det tomme ordet både et prefiks og et suffiks til et hvilket som helst ord. Alle prefikser til ord i språket
form mange prefikser av dette språket: Pref( L)
. Ligner på Suf( L)
-m kniv av suffikser Språk
.

Hvis språket L er det ingen ord L er ikke et prefiks (suffiks) til noe annet ord L, så sier de det L har prefiks (suffiks) eiendom .

La EN 1 og EN 2 – alfabeter. Hvis skjerm f:
tilfredsstiller betingelsen for alle ord
Og
, deretter kartleggingen f kalt homomorfisme .

Notater. 1. Det kan bevises at hvis f er altså en homomorfisme
.

2. Homomorfismer er ikke alltid bijeksjoner, men hver homomorfi bestemmes unikt av dens betydning på ord med én bokstav.

3. Anvende homomorfisme på språk L, får vi et annet språk f(L).

Hvis f:
- homomorfisme,
Og
, deretter gjennom f(L 1) språk er angitt
, og gjennom
språk er angitt
, og selve skjermen
kalt inversjon av homomorfisme .

Eksempler. 1. La oss si at vi ønsker å erstatte hver forekomst av tegnet 0 i strengen med tegnet EN, og hver forekomst av 1 er på bb. Da kan vi definere en homomorfisme f Så
Og
. Hvis
, Det
.

2. La f er en homomorfisme som
Og
. Deretter
Og
.

I dette kapittelet begynner vi å presentere elementene i teorien om formelle språk.

Når vi sier "formelt språk", mener vi at resultatene som presenteres her, hovedsakelig brukes til å beskrive kunstige språk oppfunnet av mennesker for spesielle formål, for eksempel programmeringsspråk. Men det er ingen uoverkommelig barriere mellom spesielt oppfunnet kunstige (formelle) språk og spontant fremkommende og utviklende naturlige språk. Det viser seg at naturlige språk er preget av komplekse grammatiske regler, dvs. er ganske stivt formalisert, og selv det mest "vitenskapelig utviklede" programmeringsspråket inneholder "mørke steder", den entydige forståelsen av dette er et problem.

Det er tre hovedaspekter å huske på når du lærer språk.

Den første er språksyntaks . Et språk er et slags sett med "ord", der et "ord" er en viss begrenset sekvens av "bokstaver" - symboler på et eller annet prefiksert alfabet. Begrepene "bokstav" og "ord" kan forstås på forskjellige måter (den matematiske definisjonen av disse begrepene vil bli gitt nedenfor). Dermed kan "bokstaver" faktisk være bokstaver i alfabetet til et naturlig eller formelt språk, for eksempel det russiske språket eller programmeringsspråket Pascal. Da vil "ordene" være endelige sekvenser av "bokstaver": krokodille, " heltall". Slike ord kalles "lexemes". Men en "bokstav" kan være et "ord" ("lexeme") som helhet. Da er "ordene" setninger av et naturlig språk eller programmeringsspråkprogrammer. Hvis et sett med "bokstaver" er fast, da vil ikke hver sekvens av dem være et "ord", dvs. et "Eleksem" av et gitt språk, men bare en sekvens som adlyder visse regler. Ordet "krykadil" er ikke et leksem på russisk, og ordet "iff" er ikke et leksem i Pascal. Setningen "Jeg elsker deg" er ikke en korrekt setning på russisk, akkurat som notasjonen "x:= =t" ikke er en korrekt skrevet Pascal-oppgaveoperatør. Syntaksen* til et språk er et system av regler som man kan konstruere “riktige” sekvenser av “bokstaver etter”. Hvert ord i et språk er preget av en bestemt struktur som er spesifikk for det aktuelle språket. Da er det nødvendig på den ene siden å utvikle mekanismer for å telle opp, eller generere, ord med en gitt struktur, og på den andre siden mekanismer for å kontrollere at et gitt ord tilhører et gitt språk. Først av alt er det disse mekanismene som studeres av den klassiske teorien om formelle språk.

Andre aspekt - språkets semantikk . Semantikk** innebærer å assosiere ordene i et språk med en viss "betydning," mening." For eksempel, når vi skriver en matematisk formel, må vi følge visse syntaktiske regler (plassering av parenteser, stavemåte av symboler, rekkefølge av symboler, etc.). ), men i tillegg har formelen en veldig bestemt betydning, den betyr noe.

Språk er et middel for kommunikasjon og overføring av informasjon. Hvis vi ønsker å bli forstått, må vi ikke bare konstruere talen vår syntaktisk korrekt, observere den riktige rekkefølgen av bokstaver i et ord og ord i en setning, men også bry oss om dens betydning, om ideene vi uttrykker i talen. Matematiske teorier om «mening» har dukket opp relativt nylig, og i tillegg til neste kapittel skal vi veldig kort se på noen tilnærminger til den matematiske beskrivelsen av programmeringsspråkenes semantikk.

* Ordet "syntaks" kommer fra det gamle greske "syn" - "sammen" og "taxier" - "orden, struktur". Dermed kan syntaks forstås som "komposisjon".

** Fra de gamle greske ordene "sema" - "tegn, omen" og "semanticos" - "betegner".

Til slutt, det tredje aspektet - språkets pragmatikk . Pragmatikk er assosiert med målene som en morsmålstaler setter for seg selv: for eksempel uttaler en person en tale med mål som ikke er relatert til syntaks, ikke til semantikken i språket han snakker eller skriver, men for eksempel til å motta en en viss sum penger for talen hans. Pragmatikk er snarere en sosiofilosofisk disiplin som påvirker individets målsettingsaktivitet. Vi vil ikke røre det det minste.

Dette kapittelet vil først undersøke de grunnleggende begrepene i den matematiske teorien om formelle språk, hvorav den viktigste er begrepet generativ grammatikk, og deretter de såkalte regulære språkene. Teorien om regulære språk danner sammen med teorien om endelige automater grunnlaget for hele teorien om formelle språk.

• Alfabet, ord, språk

• Generative grammatikker

  Som allerede nevnt, studerer den klassiske teorien om formelle språk først og fremst syntaksen til språk. Den introduserer en matematisk modell for syntaks som beskriver mekanismene for å generere og gjenkjenne "velformede" kjeder. I denne delen skal vi se på den første av disse mekanismene.

Vi kjenner operasjonene ved å kombinere språk. La oss definere operasjonene for sammenkobling og iterasjon (noen ganger kalt Kleene-lukking).

La L 1 og L 2 være språk i alfabetet

Deretter, dvs. språksammenkobling består av sammenkoblinger av alle ord på førstespråket med alle ord på andrespråket. Spesielt hvis , da , og hvis , da .

La oss introdusere notasjon for "gradene" til språket L:

Dermed inkluderer L i alle ord som kan deles inn i i påfølgende ord fra L .

Iterasjon (L) * av språket L er dannet av alle ord som kan deles inn i flere påfølgende ord fra L:

Det kan representeres ved hjelp av grader:

Det er ofte praktisk å vurdere en "avkortet" iterasjon av språket, som ikke inneholder det tomme ordet hvis det ikke finnes på språket: . Dette er ikke en ny operasjon, men bare en praktisk stenografi for uttrykket.

Merk også at hvis vi betrakter alfabetet som et begrenset språk som består av enbokstavsord, så tilsvarer den tidligere introduserte notasjonen for settet med alle ord, inkludert tomme ord, i alfabetet definisjonen av iterasjon av dette språket.

Tabellen nedenfor gir en formell induktiv definisjon vanlig uttrykk over alfabetet og språkene de representerer.

Uttrykk r	Språk L r
	L a =(a)
La r 1 og r 2 være	Lr1 og Lr2 -representerbare
vanlig uttrykk.	disse språkene.
Deretter følgende uttrykk
er regelmessige	og representerer språkene:
r=(r 1 +r 2)
r=(r 1 sirkel 2)
r=(r 1) *	L r = L r1 *

Ved opptak vanlig uttrykk Vi vil utelate sammenkoblingstegnet og anta at *-operasjonen har høyere prioritet enn sammenkobling og + , og sammenkobling har høyere prioritet enn + . Dette gjør at mange parenteser kan utelates. For eksempel, kan skrives som 10(1 * + 0) .

Definisjon 5.1. To vanlig uttrykk r og p sies å være likeverdige hvis språkene de representerer er like, dvs. Lr = Lp. I dette tilfellet skriver vi r = p.

Det er enkelt å sjekke for eksempel følgende egenskapene til vanlige operasjoner:

• r + p= p+ r (kommutativitet av foreningen),
• (r+p) +q = r + (p+q) (foreningens assosiativitet),
• (r p) q = r (p q) (assosiativitet ved sammenkobling),
• (r *) * = r * (iterasjon idempotens),
• (r +p) q = rq + pq(fordelingsevne).

Eksempel 5.1. La oss bevise, som et eksempel, en ikke så åpenbar likhet: (r + p) * = (r * p *) *.

La L 1 være språket representert ved venstre side, og L 2 ved høyre. Det tomme ordet tilhører begge språk. Hvis ordet ikke er tomt, kan det ved definisjonen av iterasjon representeres som en sammenkobling av underord som tilhører språket. Men dette språket er en delmengde av språket L"=L r * L p * (hvorfor?). Derfor . Omvendt, hvis et ord , kan det representeres som en sammenkobling av underord som tilhører språket L. Hvert av slike underord v er representert i formen v= v 1 1 ... v k 1 v 1 2 ... v l 2, hvor for alle i=1, ... , k er et underord og for alle j=1, ... , er l et underord (det er mulig at k eller l er lik 0). Men dette betyr at w er en sammenkobling av underord, som hver tilhører og derfor .