Rezumat: Operațiile înlănțuirea și limbile iterație. expresii și limbaje regulate. Exemple de expresii regulate și limbi. Construirea mașină cu stare finită expresie regulată
Expresii regulate și limbi
Expresiile regulate sunt mijloace destul de convenabile pentru construirea de „algebrică“ descrierea limbii. Acestea sunt construite din expresiile elementare prin combinarea operațiunilor (+), concatenarea () și repetare (*). Fiecare astfel corespunde expresiei r le-a transmis limba Lr. Sensul de operații de combinare de limbi străine, știm. Definim o operație concatenare și repetare (uneori numită închiderea Kleene).
Lăsați L1 și L2 - limbi în alfabetul
Apoi, că Limbile concatenare este format din concatenarea toate cuvintele din prima limbă pentru toate cuvintele de a doua limbi. În special, în cazul în care, apoi, și în cazul în care, atunci.
Vom introduce notația pentru „grade“ de limba L:
Astfel, în L i include toate cuvintele care pot fi împărțite în i cuvinte consecutive din L.
Iterație (L) * L sub formă de limbă toate cuvintele care pot fi împărțite în mai multe cuvinte consecutive de la L:
Acesta poate fi reprezentat de puteri:
Acesta este adesea convenabil să ia în considerare iterația „trunchiat“ a limbii, care nu conține un cuvânt gol. în cazul în care nu este în limba :. Aceasta nu este o operație nouă, ci pur și simplu o prescurtare convenabil pentru expresia.
De asemenea, rețineți că, dacă luăm în considerare alfabetul ca limbă de stat, constând în cuvinte-o singură literă, notația introdus anterior pentru setul de toate cuvintele, inclusiv martor, în alfabetul corespunde definiției de repetare a limbii.
Tabelul de mai jos oferă o definiție formală inductiv de expresii regulate asupra alfabetului și limbii transmise de aceștia.
Când scrieți expresii regulate va omite simbolul înlănțuirea și presupune că funcționarea * are prioritate mai mare decât concatenare, și +. și înlănțuirea - o prioritate mai mare decât +. Acest lucru va permite să omită multe paranteze. De exemplu, acesta poate fi scris ca 10 (1 * + 0).
Definiția 5.1. Două expresii regulate r și p sunt echivalente, în cazul în care reprezintă aceeași limbă, și anume, Lr = Lp. În acest caz, vom scrie r = p.
Este ușor de verificat, de exemplu, astfel de proprietăți de operații regulate:
- r + p = p + r (asociații comutativitate)
- (R + p) + q = r + (p + q) (asociații asociativitatea)
- (R p) q = r (p q) (concatenare asociativitatea)
- (R *) * = r * (idempotența iterație)
- (R + p) q = rq + pq (distributivitatii).
Exemplul 5.1. Vom dovedi, de exemplu, nu este egalitate atât de evidentă. (R + p) * = (r * p *) *.
Să L1 - limba, a prezentat partea stângă, și L2 - dreapta. cuvânt gol face parte din ambele limbi. Dacă un cuvânt care nu este gol, atunci, prin definiție, iterație este reprezentată ca o înlănțuire de subwords aparținând limbii. Dar această limbă este un subset al limbajului L „= Lr * * Lp (de ce?). Prin urmare. Pe de altă parte, în cazul în care cuvântul, atunci acesta poate fi reprezentat ca o înlănțuire de subwords care aparțin limbajului L“. Fiecare dintre aceste subwords v reprezentabile ca v = v1 v1 1 rv 1. 2. 2. vl în care pentru toți i = 1. k subword pentru toate j = 1. l subword (probabil că k este 0 sau l). Dar acest lucru înseamnă că w este concatenarea subwords, fiecare dintre care face parte și, în consecință.
Luați în considerare câteva exemple de expresii regulate și limbi pe care le reprezinta.
Exemplul 5.2. O expresie regulată (0 + 1) * este multimea tuturor cuvintelor din alfabet.
Exemplul 5.3. Expresie regulată 11 (0 + 1) * 001 este limbajul format din toate cuvintele din alfabet. care începe cu „11“ și se încheie cu „001“.
Exemplul 5.4. O expresie regulată este un limbaj format din toate cuvintele din alfabet. care nu conțin subword '000' (vezi fig. Sarcina 5.3).
Exemplul 5.5. Expresia regulată 1 * (01 * 01 *) * este limba L0ch. format din toate cuvintele din alfabet. în care un număr par de zerouri.
Într-adevăr, fiecare cuvânt de L0ch, fie nu conțin zerouri, adică, o parte a limbii, care este de 1 *. sau pot fi divizate în blocuri de forma 01 i 01 j. i, j> = 0. care precede probabil unități bloc. Expresia (01 * 01 *). definește în mod evident, o astfel de unitate, dar iterație - secvență arbitrară a unor astfel de blocuri.
Exemplul 5.6. Acum vom construi o expresie regulată. reprezentând limba L0ch1ch. care cuprinde toate cuvintele din alfabet. care conține un număr par de zerouri și un număr egal de unități.
Să w = w1 w2. WN - orice cuvânt din L0ch1ch. Apoi, desigur, n - chiar, să n = 2k. W Impartim în perechi de litere adiacente pi = w2i-1 w2i. i = 1,2. k. Există 4 tipuri de perechi: 00, 11, 01 și 10. Speciile de vapori 00 și 11 pot fi orice număr și tip de perechi 01 și 10 în mod necesar un număr par. Prin urmare, w este împărțită în blocuri, fiecare dintre care începe una dintre perechile 01 și 10 și conține un alt astfel de pereche. Fiecare astfel de bloc este descrisă de expresia (01 + 10) (00 + 11) * (01 + 10) (00 + 11) *. În acest prefix poate fi înainte de primul bloc. constând din perechi 00 și 11. Setul de cuvinte compuse din perechi 00 și 11 este dată de expresia (00 + 11) *. De aici obținem expresia R0ch1ch. L0ch1ch Setare limbă: