Kitabı oku: «Teoria d'autòmats i llenguatges formals»

2. Autòmats finits i conjunts regulars

Un autòmat finit és un dispositiu lògic que processa una cadena llegint cada símbol de la cadena només una vegada d’esquerra a dreta. L’ùnica informació que el dispositiu pot emmagatzemar és l’estat en què es troba (entre un nombre finit d’estats possibles). El dispositiu canvia d’estat només en funció del símbol que llegeix i de l’estat en què es troba abans de llegirlo.

Per exemple, es pot construir un autòmat amb dos estats que accepte el llenguatge format per totes les cadenes de longitud parella. Un estat correspondria al fet que la cadena processada fóra parella i l’altre al fet que fóra imparella. L’autòmat es trobaria inicialment en l’estat corresponent a cadena parella. La lectura de qualsevol símbol de la cadena faria canviar l’autòmat d’un estat a l’altre. L’autòmat acceptaria només aquelles cadenes que deixaren l’autòmat en el primer dels dos estats. Formalment, podem donar la definició següent:

Definició 2.1 Un autòmat finit, A, és una estructura de la forma ❬ Q, ∑, δ, q0, F ❭ on

• Q és un conjunt finit d’estats.

• ∑ és l’alfabet d’entrada.

• δ: Q × ∑ → Q és la funció de transició.

• q₀ ∈ Q és l’estat inicial.

• F ⊆ Q és el (sub)conjunt d’estats finals o d’acceptació.

Anomenem diagrama de transicions de l’autòmat A el graf dirigit en el qual hi ha un node per cada estat i un arc etiquetat amb el símbol a entre dos estats p i q si i només si δ(p, a) = q. Els nodes corresponents a l’estat inicial i als finals es marquen amb una fletxa incident i amb un doble cercle, respectivament.

L’autòmat de l’exemple anterior es podria definir formalment com a

on la funció ¿ quedaria definida per la taula següent, que s’anomena taula de transicions.

En aquesta taula, l’estat inicial es marca amb una fletxa incident i els estats finals es marquen amb un doble cercle. A vegades, es fa servir la lletra F o alguna altra marca especial al costat de l’estat o en una columna afegida per inidicar que l’estat és final. Si no s’especifica l’estat inicial s’entén que és l’estat de la primera fila de la taula.

Aquest automat es pot representar també mitjançant el seu diagrama de transicions, que es mostra a la figura 2.1

Figura 2.1: Diagrama de transicions de l’autömat A_p.

La funció de transició pot ser una funció parcial. Per tant, el comportament de l’automat pot no estar definit per a certes cadenes. Considerem l’automat següent:

L’autòmat accepta qualsevol cadena que continga només símbols a. En canvi, no té un comportament definit si la cadena d’entrada conté una b. Des del punt de vista del llenguatge acceptat per un autòmat, podem dir que l’autòmat anterior és equivalent a

L’estat yi és un estat no final del qual no es pot eixir i per tant no modifica el conjunt de cadenes acceptades per l’autòmat però, en canvi, fa que la funció δ estiga definida per a tota cadena de ∑*. Anomenem estat d’error o estat d’absorció tot estat no final que continga transicions a ell mateix amb qualsevol símbol. Anomenem també autòmat complet un autòmat tal que la seua funció de transició és total.

La funció de transició, δ, es pot estendre per a cadenes de símbols mitjançant la següent definició recursiva:

Per exemple, per a l’últim autòmat definit tindríem que

Com a norma general escriurem sempre δ tant per a la funció sobre símbols com per a la funció sobre cadenes, ja que no hi ha confusió possible.

Anomenem configuració o descripció instantània d’un autòmat finit el parell format per l’estat actual i el sufix de la cadena d’entrada que està pendent de lectura. Aquest parell defineix de forma unívoca quin serà el comportament de l’autòmat a partir d’aquest moment. Per a l’exemple anterior es tindria com a configuració inicial (q₀, aba) i com a configuració final(q₁,ε). Ens referirem al primer símbol de la cadena pendent de lectura com a símbol actual. Per exemple, donada la configuració (qo, aba), el símbol actual és a.

El pas d’una configuració a una altra en un autòmat l’anomenem moviment i el representem amb el símbol si volem fer palés que ens referim a un autòmat A en particular. Es compleix que

Expressarem una successió de moviments entre configurations mitjançant el símbol Per exemple, en el cas de l autòmat anterior tenim que

o simplement

Ja hem definit informalment el llenguatge acceptat per un autòmat com el llenguatge format per aquelles cadenes d’entrada que porten l’autòmat a un estat final. Formalment, podem utilitzar qualsevol de les dues definicions següents.

Definició 2.2 Siga un autòmat finit, A = (Q, ∑, Ö, qo, F). El llenguatge acceptat per A, que escrivim com a L(A) és donat per

o per

Diem que dos autòmats A₁ i A₂ són equivalents si L(A₁) = L(A₂).

Es diu que un estat g d’un autòmat és inabastable si no hi arriba cap transició des d’altres estats. L’autòmat resultant d’eliminar els estats inabastables és equivalent a l’autòmat original.

Dos estats p i q d’un autòmat es diuen estats idèntics si:

a) els dos són finals o no finals.

b) per a tot símbol de l’alfabet d’entrada hi ha una transició al mateix estat. És a dir, δ(p, a) = δ(q, a) per a tot a ∈ ∑.

Si en un autòmat hi ha dos o més estats idèntics, es pot canviar una transició a qualsevol d’ells per una transició a qualsevol altre i l’autòmat resultant és equivalent. En conseqüència, es poden eliminar totes les referències als estats idèntics llevat d’un, amb la qual cosa passarien a ser inabastables i es podrien eliminar.

En les pròximes seccions veurem exemples d’eliminació d’estats inabastables i idèntics.

2.1 Tipus d’autòmats finits

En aquesta secció s’introdueixen algunes generalitzacions del concepte d’autòmat finit i s’estudia la seua relació amb el model que s’acaba d’introduir.

2.1.1 Autòmats indeterministes

Imaginem que es vol construir un autòmat que accepte cadenes de {a, b, c}* que comencen en a i que acaben necessàriament en a oft¹.

Aquestes cadenes podrien ser acceptades per un autòmat com aquest

Aquest autòmat captura la idea exacta del llenguatge tal com s’ha definit i és clar que acceptarà tota cadena que comence en a i acabe en a ob i entre el primer símbol i l’últim tinga qualsevol cadena. No obstant això, en entendre l’autòmat com una màquina que processa una cadena, s’introdueix en aquest cas una novetat important que il·lustra la qüestió següent: Quin serà el comportament de l’autòmat quan es trobe en l’estasi i el símbol següent siga una a?

Podem generalitzar aquesta idea fent que la funció de transició de l’autòmat per a un estat i un símbol ens done un conjunt d’estats en comptes d’un únic estat. En aquest cas, un autòmat pot comportar-se de diverses maneres per a una mateixa cadena. Altrament dit, l’autòmat és indeterminista.

Definició 2.3 Un autòmat finit indeterminista, A, és una estructura de la forma ❬ Q, ∑, δ, q0, F ❭ on

• Q és un conjunt finit d’estats.

• ∑ és l’alfabet d’entrada.

• δ: Q × ∑ → 2Q és la funció de transició.

• q0 ∈ Q és l’estat inicial.

• F ⊆ Q és el (sub)conjunt d’estats finals o d’acceptació.

És important remarcar que l’ùnica cosa que ha canviat respecte a la definició d’autòmat finit (determinista) és la funció de transició, que ara pren com a valors conjunts d’estats en lloc d’estats simples. La taula corresponent a l’autòmat indeterminista de l’exemple seria aquesta:

De manera intuitiva, un autòmat indeterminista pot evolucionar de diverses formes amb una mateixa cadena d’entrada, però la cadena haurà de ser acceptada si d’alguna d’aquestes formes s’arriba a una configuració d’acceptació. Les diferents seqüències de configurations a què pot arribar un autòmat indeterminista es poden representar de forma convenient mitjançant un arbre.

Considerem per exemple l’autòmat anterior i la cadena aabcb. L’arbre de configuracions corresponent seria

Les fulles d’ aquest arbre de configuracions representen totes les configuracions a qué pot arribar l’autòmat. En aquest cas, l’autòmat pot arribar a quatre configurations, una de les quals és d’acceptació.

Igual que en el cas determinista, la funció de transició es pot estendre al cas de cadenes mitjançant la definició recursiva següent:

És a dir, el valor de la funció de transició des d’un estat amb una determinada cadena és igual al conjunt de tots els estats a qué es pot arribar considerant totes les possibilitats en l’autòmat indeterminista.

Atès que es treballa amb conjunts d’estats en lloc d’estats simples, la funció de transició es pot estendre també a conjunts d’estats de la manera següent:

Intuïtivament, podem pensar que un autòmat indeterminista pot trobar-se en més d’un estat al mateix temps, segons les transitions que haja seguit en els passos anteriors. Per això, el concepte de configuració d’un autòmat indeterminista inclou un conjunt d’estats. En particular, la configuració o descripció instantània d’un autòmat finit indeterminista és un parell format per un conjunt d’estats i el sufix pendent de lectura de la cadena d’entrada.

La condició perquè es done una transició entre dues configuracions és ara:

Per exemple, en el cas de l’autòmat indeterminista de l’exemple tindríem que

Considerarem que un autòmat indeterminista accepta una cadena si algun dels estats a què pot arribar en llegir tota la cadena és final. O, en unes altres paraules, si el conjunt d’estats a què arriba en llegir la cadena conté algun estat final. Aleshores, la definició formal de llenguatge acceptat per un autòmat indeterminista serà aquesta:

Definició 2.4 Siga un autòmat finit indeterminista, A = ❬ Q, ∑, δ, q0, F❭. El llenguatge acceptat per A, que escrivim com a L{A), és donat per

o per

Equivalència entre autòmats deterministes i indeterministes

Si pensem en un autòmat indeterminista com un autòmat que al mateix temps es troba en un conjunt d’estats, P, i que en l’instant següent evoluciona al conjunt d’estats donat per la funció de transició convenientment estesa, és fàcil veure que aquest autòmat ha de ser equivalent a un autòmat determinista definit sobre tots els possibles subconjunts d’estats.

Teorema 2.1 Siga A = ❬ Q, ∑, δ, q0, F ❭ un autòmat finit indeterminista. L’autòmat finit determinista A’ definit com a és la funció de transició de A estesa per a conjuntsd’ estats i , compleix que L(A) = L(A’).

La demostració és trivial a partir dels raonaments anteriorment exposats. Per a qualsevol cadena de L{A) es té que

on P és un conjunt que conté almenys un estat final.

Aquesta seqüència de transicions es correspondria exactament amb una seqüència de transitions per a a’ on cada configuració tindria un únic estat (un element de 2^Q) i una cadena. Òbviament, l’estat P al qual s’arriba pertany a F’ segons la definició.

Com a exemple podem escriure l’autòmat determinista equivalent a l’autòmat indeterminista de l’exemple anterior. La nova taula de l’autòmat contindrà, per a tot possible conjunt d’estats, P, i per a tot símbol, x, el valor:

Aleshores s’obté la taula següent:

Estrictament, caldria completar la taula amb una entrada per cada possible subconjunt d’estats. No obstant això, en aquest cas (i en molts altres), no té sentit ferlo perqué aquests nous estats no serien abastables des de {g₀} (no apareixen en cap lloc de la taula de transitions). De fet, en aquest cas l’estat {<72} tampoc no apareix a la taula i no serà, doncs, abastable. L’estat 0 sí que és abastable però, com que serà sempre un estat d’error, en podem prescindir. Amb aquestes consideracions, l’autòmat resultant es pot escriure com a

Un cas particular d’autòmat indeterminista són els autòmats amb més d’un estat inicial. Un autòmat indeterminista de la forma A = (Q, ∑, 5,1, F), on Iés el conjunt d’estats inicials, no és més que un autòmat indeterminista on la configuració inicial, donada una cadena x, és

(I, x)

A l’hora de calcular l’autòmat determinista equivalent només cal tenir en compte que el nou estat / serà l’ùnic estat inicial.

Per exemple, siga l’autòmat

la taula del qual és

L’ autòmat determinista equivalent seria aquest:

O en forma de diagrama

2.1.2 Autòmats amb transicions buides

Una altra generalització de l’autòmat finit determinista consisteix a incloure-hi la possibilitat de canviar d’estat sense consumir cap símbol a l’entrada. Això dóna lloc al que es coneix com a transicions buides o transicions nul·les.

Definició 2.5 Un autòmat finit amb transicions buides, A, és una estructura de la forma A — ❬ Q, ∑, δ, q0, F ❭ on

• Q és un conjunt finit d’estats.

• ∑ és l’alfabet d’entrada.

• és la funció de transició.

• q0 ∈ Q és l’estat inicial.

• F ⊆ Q és el (sub)conjunt d’estats finals o d’acceptació.

Definit d’aquesta manera, l’autòmat finit amb transicions buides constitueix una generalització dels autòmats indeterministes.

D’altra banda, les transicions buides introdueixen un altre tipus d’indeterminisme en l’autòmat: trobar-se en un determinat estat o en un altre estat connectat amb l’anterior mitjançant transicions buides és la mateixa cosa (encara que no en els dos sentits). Per relacionar aquest tipus d’autòmats amb els anteriors, considerarem també que l’autòmat es pot trobar en més d’un estat alhora i que evoluciona a altres estats en funció de quines siguen les transicions. Per tal de formalitzar-ho resulta útil introduir el concepte de tancament èpsilon o e-tancament.

Definició 2.6 El tancament èpsilon d’un estat q en un autòmat amb transicions buides, escrit com aq*, és donat pel conjunt d’estats a què es pot arribar des de q només amb transicions buides. El tancament èpsilon d’un conjunt d’estats P es defineix com a

El concepte de tancament èpsilon representa el fet que l’autòmat, en qualsevol moment, pot canviar a qualsevol estat que estiga connectat amb transicions buides sense consumir símbols. Podem ara definir una funció de transició associada a l’autòmat sobre cadenes que tinga en compte aquest fet mitjançant la definició recursiva següent:

En aquesta definició, hem considérât la funció de transido, 5, estesa per a conjunts d’estats. Donada qualsevol funció de transido definida sobre estats, sempre serà possible aplicar-la sobre conjunts d’estats de la manera següent:

Aquesta extensió serà vàlida tant si x és un símbol com si és una cadena. Normalment, sabrem si ens referim a una o a l’altra versió en funció deis arguments. I no pot haver-hi confusió, ja que sempre es compleix que δ({q}, x) = δ(q, x).

La definició recursiva de la funció ô’ captura de forma natural les possibles transicions buides que pot efectuar l’automat entre dos simbols consecutius qualssevol. En la figura 2.2 es representa aquesta idea gràficament.

Figura 2.2: Representado gràfica del càlcul recursiu de ô’(q, wa). La linia continua representa el conjunt ô’(q, w) i la linia discontinua és Posteriorment caldria calcular el tancament epsilon d’aquest darrer conjunt.

El concepte de configuració no canvia respecte al que s’ha introduit per a automats indeterministes. Només cal tenir en compte que la funció de transido és ara ô’. El llenguatge acceptât per un automat amb transicions buides es pot, dones, definir de la manera següent:

Definido 2.7 Siga un autômat finit amb transicions buides, ❬Q, ∑, δ, q0, F❭. El llenguatge acceptai per A, que escrivim com a L(A), és donat per

o per

Considerem com a exemple l’autòmat següent, que accepta cadenes de {a, b}* que tinguen un nombre parell de símbols a o b.

La taula de transitions corresponent, a la qual hem afegit una columna per incloure-hi els corresponents tancaments èpsilon, seria:

Fem notar que, si bé en el diagrama només hi ha dues transicions buides, és bastant evident que, a més a més, tot estat conté implícitament una transició buida a ell mateix.

Equivalència entre els autòmats amb transicions buides i sense

Encara que el funcionament de les transicions buides és clarament diferent, l’efecte és que aquests autòmats es comporten com els autòmats indeterministes. A cada moment es troben en un conjunt d’estats determinat i en l’instant següent evolucionen a un altre conjunt d’estats donat per la funció de transició estesa que s’acaba de definir.

Teorema 2.2 Siga A = ❬Q, ∑, δ, q0, F❭ un autòmat finit amb transicions buides. L’autòmat finit indeterminista A’, definit com a A’ = ❬Q, ∑, δ’, q₀, F❭, on δ’ és la funció de transició de A estesa per a cadenes i F’ = {q ∈ Q | q• ∩ F ≠ θ}, compleix que L(A) = L(A’).

Com que la funció 5’ té implícitament en compte totes les possibilitats a l’hora de canviar d’estat sense consumir símbols, l’autòmat així definit és indeterminista i equivalent a l’original.

Com a exemple de la construcció que suggereix aquest teorema es pot calcular l’autòmat indeterminista equivalent a l’autòmat amb transicions buides de l’últim exemple. Amb aquesta finalitat, hem de calcular totes les positions de la nova taula de transitions com a S’(q, a) que per definició és igual a

Per exemple,

i, de la mateixa manera, totes les altres entrades de la taula. Al final s’obté

Aquest autòmat indeterminista es pot transformar en determinista si considerem els estats com a conjunts d’estats i hi afegim a més a més els conjunts d’estats següents:

A partir de les dues últimes taules es pot veure que els estats {q₁}, {q₂}, {q₃} i {q₄} no són abastables des de l’estat inicial i també que els estats {q₀} i {q₁,q₂} són equivalents. Amb tot això, l’autòmat que finalment s’obté és

on hem anomenat els estats segons els subíndexs dels conjunts corresponents (per exemple, 23 ≡ {q₂, q₃}).

2.2 Autòmats finits i llenguatges regulars

Els diferents tipus d’autòmats finits introduits fins ara accepten els mateixos llenguatges. En unes altres paraules, defineixen una certa classe de llenguatges. El que ens interessa ara és relacionar aquesta classe de llenguatges amb la jerarquia de Chomsky. En particular, es demostrarà que els llenguatges acceptats per autòmats finits i els llenguatges regulars són la mateixa classe.

2.2.1 Gramàtica equivalent a un autòmat finit

Considerem el llenguatge acceptat per un autòmat finit determinista. Per a qualsevol cadena, iu, d’aquest llenguatge es té que

En cada pas en aquesta seqüència de configurations, desapareix un símbol de la cadena i s’evoluciona a un nou estat. Un canvi de configuració es dóna només si existeix la transició adequada en l’autòmat.

Aquest procés es pot relacionar directament amb la forma en què les gramàtiques regulars generen cadenes. Una derivació directa només es dóna si hi ha una producció adequada i l’efecte és que en la forma sentencial apareix un nou símbol terminal. Si es fa la identificació d’estats amb símbols no terminals i de transicions amb produccions, el procés d’acceptació i de derivació d’una cadena són equivalents.

Teorema 2.3 Siga un autòmat finit determinista A = ❬Q, ∑, δ, q0, F❭. La gramàtica regular G = ❬VT, VN, P, S❭, on VT = ∑, V_N = Q, S = q₀ i el conjunt de produccions és donat per

compleix que L(A) = L(G).

La demostració del teorema és trivial a partir de l’explicació anterior. Si una cadena x és acceptada per l’autòmat és perque hi ha una computació de la forma

on s’han aplicat exactament |x| transicions de la forma δ(q_i, x_i) = q_i+1 i xi és l’i-ésim símbol de x per a valors í = 1,2,..., |x|.

Aleshores, a partir de l’axioma, y₀, i aplicant-hi les corresponents produccions qi → x_iq_i+1 s’obté la derivació

exactament amb els mateixos passos que la computació anterior. Finalment, com que y és final, aplicant-hi la producció q → ε s’obté la cadena x, la qual cosa significa que aquesta és generada per la gramàtica.

La construcció que suggereix el teorema es pot resumir gràficament de la manera següent:

Exemple 2.1 Calculem ara una gramàtica regular equivalent a l’últim autòmat obtingut en la secció 2.1.2 (pàgina 47).

En primer lloc, tornarem a anomenar els estats en sentit horari des de l’inicial com a S, A, B i C. D’aquesta manera, noms d’estats i de símbols no terminals coincidiran exactament. Calculant les produccions corresponents a cada una de les transicions de l’autòmat, s’arriba a la gramàtica

S → aA\bC\ε

A → aS\bB\ε

B → bA\aC

C → aB\bS\ε

2.2.2 Autòmat equivalent a una gramàtica regular

A partir de la definició de gramàtica regular, és clar que per a qualsevol cadena w d’un llenguatge regular ha d’existir una derivació de la forma

per a alguna gramàtica regular G = ❬VT, VN, P, S❭. Totes les formes sentencials α_i han de complir necessàriament que ∈ VT* • VN.

En cada pas s’aplica una de les produccions de la gramàtica, que fa que apareguen uns certs símbols en la forma sentencial en lloc del (únic) símbol no terminal. Donat un determinat símbol no terminal en una forma sentencial, hi ha un nombre finit de produccions possibles que s’hi poden aplicar.

En el teorema següent, es defineix un autòmat que simula el procés de derivació de cadenes d’una gramàtica qualsevol, de forma que aquest accepta només aquelles cadenes que són generades per la gramàtica.

Teorema 2.4 Siga una gramàtica regular G = ❬VT, VN, P, S❭. L’autòmat finit amb transicions buides A = ❬Q,∑,q_S,δ,{q_ε}❭, amb ∑ = VT,

la funció de transició tal que

compleix que L(A) = L(G).

L’autòmat així definit simula a) el procés de reescriptura d’un símbol no terminal com les corresponents parts dretes de produccions associades, i b) la generació dels símbols terminals associats a cada part dreta de producció.

La construcció suggerida pel teorema es resumeix gràficament en aquests dos quadres.

L’autòmat que simula una gramàtica definit en el teorema anterior es pot calcular per a qualsevol gramàtica regular. No obstant això, en la majoria de casos els autòmats que s’obtenen són grans i excessivament complexos (en part per l’abundància de transicions buides). És possible donar un mètode simplificat per a l’obtenció de l’autòmat equivalent a una gramàtica que restringeix mínimament la forma de les produccions però, en canvi, obté normalment autòmats relativament compactes.

Mètode per a l’obtenció de l’autòmat equivalent a una gramàtica regular

Si una gramàtica regular compleix que cap producció no té més d’un símbol terminal en la part dreta, es pot obtenir el seu autòmat finit equivalent mitjançant el mètode següent:

Siga G = ❬V_T, V_N, P, S❭ una gramàtica regular en què totes les productions de P són de la forma A → a, on |a|_vT ≤ 1.

Aleshores, l’autòmat A = ❬Q, VT, δ, qs, {q_F}), on

i la funció de transició del qual és donada per

compleix que L(A) = L(G).

La construcció suggerida es mostra gràficament a continuació.

En l’exemple següent s’il·lustra la diferència entre la construcció suggerida pel teorema anterior i el mètode que s’acaba d’introduir.

Exemple 2.2 Construïu un autòmat finit determinista equivalent a la gramàtica:

Autòmat obtingut a partir del teorema

La construcció suggerida pel teorema dóna com a resultat un autòmat amb la següent taula de transicions, on s’ha afegit també informació sobre els tancaments èpsilon i s’ha relaxat una mica la notació de conjunts (el guionet en les columnes corresponents a símbols significa 0, però en la columna de e vol dir que ¿(y, e) només conté y).

El diagrama de transicions corresponent seria:

A partir d’aquest diagrama s’obtindria l’autòmat indeterminista la taula de transicions del qual és

on

Per a fer aquest autòmat determinista cal afegir a la taula les entrades següents:

Molts dels estats obtinguts no són abastables i, al final, l’autòmat es pot escriureen funció dels estats S, Q₁, Q₂, ε i B• (queés idèntic a B).

Autòmat obtingut mitjançant el mètode alternatiu

Per a aplicar el mètode alternatiu a la gramàtica de partida, de primer cal transformar les produccions A → baB i B → aa, que no compleixen la condició exigida pel mètode, en les produccions A → bC, C → aB, B → aD i D → b, on C i D són símbols no terminals nous.

Aleshores s’obté que

Si escrivim directament la taula de transicions del corresponent autòmat indeterminista (incloent-hi també els tancaments èpsilon) així com les entrades corresponents per a ferlo determinista, s’obté que

d’on directament, després d’eliminar els estats no abastables, s’arriba al mateix autòmat determinista que en el cas anterior, on els antics estats Q₁, Q₂ i ε són ara ABDF, ACF i F, respectivament.

2.3 Expressions regulars

Les anomenades expressions regulars són fórmules que utilitzen operacions simples sobre símbols que serveixen per definir conjunts de cadenes que reben el nom de conjunts regulars.

Aquestes expressions van ser introduïdes de forma independent dels autòmats i les gramàtiques i tenen un gran interés tant teòric com pràctic.

2.3.1 Conjunts i expressions regulars

Una expressió regular representa un únic conjunt de cadenes sobre un determinat alfabet. L’operador binari “+” aplicat sobre expressions regulars representa la unió dels corresponents conjunts, mentre que els operadors “•” i “*” (aquest últim unari) representen la concatenació i el tancament dels corresponents conjunts, respectivament.

La definició formal d’expressió regular és una descripció exhaustiva de les seues possibilitats en forma recursiva. Separarem en les definicions següents la sintaxi i la semàntica associada a les expressions regulars.

Definició 2.8 Siga Y, un alfabet determinat:

1. ε, 0 i α són expressions regulars, Vα ∈ ∑

2. si α i ß són expressions regulars, aleshores α + ß també.

3. si α i ß són expressions regulars, aleshores α • ß o α ß també.

4. si a és una expressió regular, aleshores α* també.

5. si α és una expressió regular, aleshores (α) també.

6. només són expressions regulars les que s’obtenen mitjançant l’aplicació de les regles anteriors.

Aquesta definició només descriu la sintaxi, però no diu quines cadenes estan associades a cada expressió regular. Si escrivim com a L(a) el conjunt regular representat per una expressió regular cc, aleshores tenim que

Amb aquestes regles, podem definir formalment conjunt regular com tot conjunt de cadenes, L, per al qual existeix una expressió regular, a, tal que L = L(α).

Alguns exemples de conjunts regulars sobre l’alfabet {a, b} són aquests:

Normalment, no distingirem entre expressió regular, a, i llenguatge representat per una expressió regular, L(a). Tret que explícitament es diga el contrari, ens referirem a tots dos com a a.

2.3.2 Propietats

Les expressions regulars compleixen certes propietats que són en realitat propietats dels conjunts de cadenes i de les operacions unió, concatenació i tancament. Tanmateix, és convenient repetirles ara per tal de manipular i simplificar expressions regulars.

En primer lloc, enumerarem les propietats relatives als operadors bàsics amb conjunts. Escriurem a ,ß i 7 per representar expressions regulars qualssevol.

D’altra banda, utilitzarem algunes simplifications i extensions a l’hora d’escriure expressions regulars com a α+ per representar α*α = αα*, o α² en lloc de αα, entre altres. Considerarem aquestes expressions com a regulars a tots els efectes, ja que tenen una traducció directa a expressió regular sintàcticament correcta segons la definició que se n’ha donat. En canvi, una expressió com ααα* no pot ser considerada com a expressió regular. Encara que el seu significat és perfectament clar, la seua traducció a una expressió regular segons la definició no és, ni de bon tros, directa.

2.3.3 Equivalències

Teorema 2.5 Donada qualsevol expressió regular, γ, el llenguatge L(γ) és regular.

La demostració es fa per inducció sobre la longitud² de l’expressió regular i consisteix a trobar un autòmat finit equivalent:

B.I. Les úniques expressions de longitud 1 són, ε, 0 i a. I per a aquestes hi ha els autòmats següents, que són trivialment equivalents.

H. I. Qualsevol expressió regular de longitud menor estrictament que n representa un llenguatge regular.

P.I. Siga γ una expressió regular de longitud n. Pot haver-hi 4 casos:

1. γ = (α), amb la qual cosa |α| = n — 2 i L(γ) = L (α) és regular per hipòtesi d’inducció.

2. γ = α + ß, amb la qual cosa tant a com ß han de tenir longituds menors o iguals que n — 2 i representaran llenguatges regulars per hipòtesi d’inducció. Suposem que A_a i Aß són autòmats finits que accepten L(α) i L(ß),respectivament. L’autòmat construit mitjançant els dos autòmats anteriors i un nou estat inicial des del qual ixen dues transicions buides, una a cada un dels vells estats inicials, accepta trivialment el llenguatge

3. γ = α • ß, en aquest cas es faria una construcció similar amb els autòmats corresponents a a i /?, però ara el nou estat inicial seria l’inicial de a, els nous finals serien només els de β i els vells finals de a estarien units al vell inicial de /? mitjançant transicions buides.

4. γ = α*, en aquest cas L(a) també és regular per hipòtesi d’inducció i la construcció que caldria fer consistiria a afegir un nou estat inicial que seria també final (per acceptar e), unit mitjançant una transició buida al vell estat inicial. A aquest estat arribarien a més a més transicions buides de tots els estats finals de A_a.

Les tres construccions emprades en aquest teorema es mostren gràficament en la figura 2.3. L’autòmat associat a cada expressió regular, A_a, es mostra com a , on el cercle de l’esquerra representa l’estat inicial i el cercle de la dreta representa tots els estats finals. En les construccions, només els estats finals definitius es representen com a cercles dobles. Una transició que ix del cercle de la dreta d’un autòmat (que pintarem com una fletxa doble) representa una transició per cada estat final original en aquest autòmat.

Teorema 2.6 Donat un autòmat finit, A, existeix una expressió regular, oa, tal que L(A) — L(α_A).

Siga A = ❬Q, ∑, δ, q₁, F), on , i definim com a el conjunt de cadenes de →* que permeten l’autòmat passar des de l’estat q_i fins a l’estat qj sense passar per cap estat «major» que k com a estat intermedi. És a dir,

Figura 2.3: Diferents combinacions d’autòmats en funció de A_α i Aß. a) A_α+ß, b)A_αß i c) A_α*.

on Pr(x) és el conjunt de prefixos de la cadena.

Si k = 0, els conjunts corresponents són finits i donats per

on E = {ε} si i = j o si no E = 0.

Per a qualsevol altre valor de fc, aquests conjunts es poden definir de forma recursiva segons

Aquesta expressió recursiva il·lustra el fet que les cadenes noves de que no estan incloses en són exactament aquelles que per anar dei a jpassen una vegada o més per l’estat fc. Per tant, es poden factoritzar com les cadenes que arriben a fc, les que iteren sobre fc zero vegades o més i les que van de fc a j i en tots els casos fent servir estats intermedis inferiors a fc. Aquesta factorització es mostra gràficament en la figura 2.4.

A continuació es demostra per inducció sobre k que tots els són conjunts regulars.

B.I. Per a tot existeix una expressio que representa un nombre finit de cadenes d’un sol símbol segons que hi haja transcicions entre els estats ¿ i j o no.

H.I. Suposem que es compleix que per a alguna expressió regular

P.I. Considerem el conjunt . Segons la definició recursiva d’abans, aquest conjunt es pot representar mitjançant unió, concatenació i tancament de conjunts que compleixen la hipòtesi d’inducció. Aleshores,

Per tant, és una expressió regular que representa el conjunt

Figura 2.4: il·lustració de la factorització que dóna lloc a la definició recursiva dels conjunts .

Com que per a l’autòmat A es compleix que , aleshores es té que el llenguatge acceptat per A es pot representar mitjançant l’expressió regular

on és l’expressió regular corresponent a .

2.3.4 Càlcul de l’expressió regular equivalent a un autòmat

Encara que la demostració del teorema anterior es pot fer servir per calcular l’expressió regular equivalent a un autòmat qualsevol, la seua aplicació resulta normalment llarga i tediosa.

Una forma més gràfica de resoldre el mateix problema es basa en la definició dels autòmats d’expressions regulars.

Un autòmat d’expressions regulars (o e-autòmat) és un autòmat en el qual les transicions estan etiquetades amb expressions regulars. L’autòmat passa d’un estat a un altre en llegir de la cadena d’entrada qualsevol prefix inclòs en el conjunt regular de la corresponent transició.

Podem considerar el següent e-autòmat com a exemple.

La etiqueta en la transició incident de l’estat inicial significa que es poden consumir símbols de la cadena d’entrada abans de començar. Per exemple, amb la cadena aa com a entrada, les possibles configurations inicials d’aquest e-autòmat serien (1, aa) i (1, a). En la segona s’ha llegit a que pertany a l’expressió regular a + e.

A partir de la primera de les configurations inicials, l’autòmat podria seguir qualsevol d’aquestes successions de configurations:

De les quatre configurations a qué l’autòmat pot arribar, la segona i la quarta són d’acceptació.

Els e-autòmats són indeterministes en general i segueixen el mateix criteri d’acceptació que els autòmats finits indeterministes.

Equivalència amb els autòmats finits

Un autòmat finit és un autòmat d’expressions regulars on totes aquestes són de la forma α, ε o 0.

En l’altre sentit, l’equivaléncia també és bastant intuitiva a partir del fet que les cadenes acceptades per un autòmat d’expressions regulars han de pertànyer necessàriament a la concatenació, unió i/o tancament de certes expressions regulars. Per tant, el llenguatge finalment acceptat ha de ser regular.

Per exemple, l’e-autòmat anterior seria equivalent a l’autòmat següent:

En aquesta representació, les caixes representen els autòmats corresponents a cada una de les expressions regulars.

Representació

Un e-autòmat de n estats és donat per un conjunt de n + n2 expressions regulars, que representarem si interessa com una taula.

La taula corresponent a l’últim exemple seria

És important observar que, com es posa de manifest en la taula, l’absència de transicions és equivalent a una transició etiquetada amb 0. I també que tot estat conté sempre (encara que normalment no la inclourem en el diagrama) una transició a ell mateix etiquetada amb ε.

A partir de les expressions de la taula, es poden caracteritzar també els estats inicials de l’e-autòmat com aquells estats q_j, tals que α_0j ≠ 0.

Eliminació d’estats en e-autòmats

Donat un autòmat d’expressions regulars, sempre es pot eliminar un dels seus estats i modificar les transicions adjacents de forma que el llenguatge acceptat no canvie (sempre que l’estat eliminat no siga final).

Veient l’autòmat com una taula, l’eliminació de l’estat fc es correspondria amb l’eliminació de la fila i columna fc. Perquè es mantinguera el llenguatge acceptat per l’autòmat, totes les expressions en la taula resultant, a^, s’haurien d’actualitzar al nou valor:

Figura 2.5: Representació gràfica del procés d’eliminació d’un estat, k, en un e-autòmat. Per cada parell d’estats i ij amb transicions respecte de k com en la figura, cal actualitzar l’expressió α_ij.

Aquesta actualització es correspon només a afegir³ transicions en l’autòmat entre els nodes que estaven connectats a través de l’estat fc. Aquesta situació es representa gràficament en la figura 2.5.

Per exemple, l’autòmat de l’exemple anterior amb l’estat 2 eliminat donaria com a resultat

Un estat inicial es pot eliminar sempre que el corresponent estat j (serà en general més d’un) esdevinga un nou estat inicial i la seua «transició d’entrada» estiga etiquetada amb akk*α_kj. En cas que j ja fóra inicial, l’expressió anterior se sumaria a la que poguera estar associada a j.

El resultat d’eliminar l’estat inicial en l’autòmat de l’exemple seria

Si ara eliminem l’estat 2 en aquest autòmat obtenim

O de forma equivalent

que és el mateix que s’obtindria de l’eliminació de l’estat 1 en l’e-autòmat format pels estats 1 i 3.

Obtenció de Vexpressió regular equivalent a un e-autòmat

Donat un e-autòmat, sempre és possible arribar a un e-autòmat de la forma

per cada estat final de l’autòmat inicial. Aquest e-autòmat d’un únic estat final representa totes les cadenes que porten l’autòmat original fins a l’estat i-èsim. És a dir, el conjunt Per tant, com que

l‘expressió regular equivalent a l’autòmat de partida serà

Exemple 2.3 Calculeu l’expressió regular equivalent a l’autòmat següent

Si s ‘ elimina de primer l ‘ estat 4 i després l ‘ estat 2 s ‘ obté, respectivament,

En eliminar cada un dels estats finals s obtenen els e-autòmats següents:

a partir dels quals es pot escriure la expressió regular equivalent, que seria

2.4 Exercicis

Exercici 2.1 Comproveu i justifiqueu que el métode per passar d’un autòmat a una gramàtica equivalent segueix sent vàlid per a autòmats indeterministes i amb transicions épsilon.

Exercici 2.2 Trobeu un autòmat finit determinista simple que accepte totes les cadenes de zeros i uns en les quals tot símbol 0 tinga un símbol 1 a continuació.

Exercici 2.3 Trobeu un autòmat finit determinista simple que accepte totes les cadenes de {0,1}* que continguen la subcadena 010 o la subcadena 101.

Exercici 2.4 Trobeu un autòmat finit determinista com més senzill millor que accepte totes les cadenes de {0,1}* que acaben en 101 o 011.

Exercici 2.5 Siga A = ❬Q, ∑,δ,I, F❭, on I és el conjunt d’estats inicials. Descriviu matemàticament el llenguatge acceptat per l’autòmat A

Exercici 2.6 Digueu si són equivalents els autòmats següents:

Exercici 2.7 Trobeu autòmats finits deterministes equivalents als autòmats següents:

Exercici 2.8 Doneu un mètode general que, a partir d ‘ un autòmat A, obtinga un altre autòmat A’, de forma que L(A) = L(A’)R. És a dir, A’ accepta el mateix llenguatge que A però invertit. Apliqueu el mètode als autòmats de la pregunta anterior.

Exercici 2.9 Doneu un mètode general que, a partir d ‘ un autòmat A, obtinga un altre autòmat A’, de forma que L(A) = L(A’). És a dir, A’ accepta el complementari del llenguatge que accepta A. Apliqueu el mètode als autòmats de la pregunta anterior.

Exercici 2.10 Trobeu gramàtiques regulars equivalents als autòmats de les preguntes anteriors.

Exercici 2.11 Trobeu un autòmat finit determinista equivalent a la gramàtica donada per les produccions següents:

Exercici 2.12 Trobeu un autòmat finit determinista que accepte les cadenes generades per la gramàtica següent:

Exercici 2.13 Construiu autòmats deterministes equivalents a les expressions regulars següents:

Exercici 2.14 Calculeu les expressions regulars corresponents als autòmats dels exercicis anteriors.

Exercici 2.15 Trobeu les expressions regulars corresponents als llenguatges complementaris acceptats pels autòmats de l’exercici anterior.

Exercici 2.16 Calculeu una expressió regular equivalent al llenguatge format per cadenes w de {a, b}* tals que |w|_a és parell i |w|_b és imparell.

Exercici 2.17 Trobeu una expressió regular per al llenguatge format per qualsevol cadena de {a, b, c}* de longitud parella i que no acabe en a.

Exercici 2.18 Una extensió interessant dels autòmats finits són les anomenades màquines seqüencials o d’estats finits, que són autòmats finits que poden donar com a resultat (una cadena de) símbols. En particular, una màquina seqüencial de Mealy és un autòmat finit al qual s’afegeix una funció d’eixida de la forma γ: Q × ∑ → , on és l’alfabet d’eixida. A mesura que es llegeix una cadena d’entrada es forma una cadena d’eixida o, el que és el mateix, la màquina computa una certa funció de ∑* en *. A més a més, a cada màquina li correspon tant un llenguatge d’entrada com un d’eixida. El primer són les cadenes de ∑* que porten la màquina a un estat final, i el segon està format per la unió de les corresponents cadenes d’eixida. Formalitzeu els conceptes anteriors i demostreu que tant el llenguatge d’entrada com el d’eixida han de ser regulars. Calculeu quins són aquests llenguatges en el cas de la màquina següent.

Exercici 2.19 Una alternativa a la màquina de l’exercici anterior és l’anomenada màquina seqüencial de Moore, que consisteix a associar els símbols d’eixida als estats i no a les transicions entre estats. És a dir, la funció d’eixida té la forma γ: Q → A. Aquesta màquina sempre dóna com a eixida el símbol associat a l’estat inicial abans de llegir cap símbol a l’entrada. Demostreu que les dues formes de definir les màquines d’estats finits són equivalents. (Dues màquines són equivalents si calculen la mateixa funció de ∑* en *.) Calculeu els llenguatges d’entrada i eixida de la màquina de Moore que es dóna a continuació i calculeu una màquina de Mealy equivalent. Calculeu també una màquina de Moore equivalent a la màquina de l’exercici anterior.

¹ És a dir, el llenguatge seria {a} {a, b, c}* {a, b}

² Entesa com a nombre de símbols que fan falta per escriure-la.

³ En realitat, caldria parlar de modificació de transicions. Però aquestes modificacions sempre «afegeixen» noves formes de connectar els dos estats implicats.