Lenguaiges regulares

Na teorie de la ciéncia de la cumputaçon i teorie formal de lenguaige, ua lenguaige regular ye ua lenguaige formal que puode ser spressa usando spressones regulares. Note que ls recursos de las "spressones regulares" fornecidas cun bárias lenguaiges de porgramaçon son oumentada cun caratelísticas que las tornan capazes de recoincer lenguaiges que nun puoden ser spressas por spressones regulares formales (cumo formalmente ye defenido ambaixo).

Na hierarquia de chomsky, lenguaiges regulares son defenidas para ser lenguaiges que son geradas por gramáticas tipo 3 (gramática regulares). Lenguaiges regulares son mui úteles na análeze d'antradas i ne l porjeto dua lenguaige de porgramaçon.

Defeniçon Formal

La coleçon de lenguaiges regulares subre un alfabeto Σ ye defenida recursibamente seguindo las regras ambaixo:

La lenguaige bazie Ø ye ua lenguaige regular.
La lenguaige cadeia bazie {ε} ye ua lenguaige regular.
Para cada la ∈ Σ (la pertence la Σ), la lenguaige de l cunjunto unitairo {la} ye ua lenguaige regular.
Se La i B son lenguaiges regulares, anton La ∪ B (ounion), La • B (cuncatenaçon), i La* (Fecho de Klene ó streilha) son lenguaiges regulares.
Nanhue outra lenguaige subre Σ ye regular.

Beija Spresson regular para ber la semántica i la síntaxe dessas ouparaçones. Note que ls causos arriba son cunsequéncias de las regras de la defeniçon de las spressones regulares.

Eisemplos

To lenguaige fenita ye regular. Outros eisemplos típicos ancluen la lenguaige cunsistindo de todas las cadeias subre l'alfabeto {la,b} que cuntenhan un númaro par de las, ó la lenguaige cunsistindo de todas las cadeias de la forma: bários las seguido por bários bs.

Un simples eisemplo de lenguaige que nun ye regular ye l cunjunto de cadeias $\{a^{n}b^{n}\,\vert \;n\geq 0\}$ . Esso porque nessa lenguaige, l númaro de las cuntrola l númaro de bs, que nun son permitidos por qualquiera ua de las regras arriba. Ber mais an Lema de l bombeamiento para lenguaiges regulares.

Eiquibaléncia cun outros formalismos

Ua lenguaige regular sastifaç las seguintes propiadades que son eiquibalentes:

eilha puode ser aceita por un outómato fenito determinístico.
eilha puode ser aceita por un outómato fenito nó-determinístico.
eilha puode ser aceita por un outómato fenito altarnado.
eilha puode ser gerada por ua gramática regular.
eilha puode ser gerada por ua gramática de prefixos.
eilha puode ser aceita por ua leitura de Máquina de Turing.
eilha puode ser defenida nun monádico de la lógica de segunda orde.
eilha ye l cunjunto eimaige dun subconjunto dun monóide fenito sob un homomorfismo de l monóide libre an sou alfabeto.
eilha puode ser reconhecida por algua Monoide fenitamente gerada.

Las propiadades arriba son ousadas, ocasionalmente, cumo un defeniçon altarnatiba de las lenguaiges regulares.

Resultados subre la Cumplexidade

Na teorie de la cumplexidade cumputacional, la classe de cumplexidade de todas lenguaiges regulares son ocasionalmente chamadas cumo REGULAR ó REG i eiquibale la DSPACE(L(1)), l porblema de decison puode ser resolbido nun spácio custante (l spácio ousado ye andependiente de l tamanho de l'antrada). REGULAR ≠ AC⁰, ua beç que REG (trebialmente) cuntén l porblema de la paridade de detreminar se l númaro de bits 1 na antrada ye par ó ímpar i este porblema nun stá naAC⁰.^[1] An cuntrapartida, REGULAR nun cuntén AC⁰, porque las lenguaiges nun regular de ls palíndromos, ó la lenguagen nun regular $\{0^{m}1^{m}:m\in \mathbb {N} \}$ , ambas, puoden ser reconhecidas an AC⁰.^[2]

Se ua lenguaige ye nó regular, eilha requer ua máquina que ne l mínimo Ω(log log m) de spácio para reconhecé-la (adonde m ye l tamaho de l'antrada).^[3] An outras palabras, DSPACE(L(log log m)) ye eiquibalente la classe de las lenguaiges regulares. Na prática, grande parte de las lenguaiges nun regulares son resolbidas por máquinas que tenga ne l mínimo spácio logarítmico.

Propiadades de Fechamiento

Las lenguaiges regulares son cerradas subre bárias ouparaçones, ó seia, se ua lenguaige K i L son regulares, anton l resultado de las seguintes ouparaçones tamien ye regular:

las ouparaçones teóricas de cunjunto: ounion $K\cup L$ , anterseçon $K\cap L$ , i cumplemiento ${\bar {L}}$ . Por bias desso, defrença $K-L$ tamien ye bálida, yá que ye cumpuosta pula anterseçon i pul cumplemiento.
las ouparaçones regulares: ounion $K\cup L$ , cuncatenaçon $K\circ L$ i streilha $L^{*}$ .
las ouparaçones de la família de lenguaiges abstratas: cadeia homomórfica, cadeia ambesa homomórfica, i anterseçon cun lenguaiges regulares. Cumo cunsequéncia, eilhas son cerradas sob arbitrária estados fenitos trasduçones, cumo quociente $K/L$ cun ua lenguaige regular. Para alhá desso, las lenguaiges regulares son cerradas sob quocientes cun lénguas arbitrárias: Se L ye regular, anton L / K ye regular para qualquiera K.
l reberso (ó eimaige spelhada) $L^{R}$ .

Decidindo se ua lenguaige ye regular

Hierarquia de Chomsky

Al localizar las lenguaiges regulares na hierarquia de Chomsky, ouserbe que todas las lenguaiges regulares son libres de cuntesto. L cuntrairo yá nun ye berdadeiro: por eisemplo, ua lenguaige que cunsiste de todas las strings tenendo l mesmo númaro de la's i de b's ye libre de cuntesto mas nun ye regular. Para probar que ua lenguaige cumo essa nun ye regular, usamos l Teorema de Myhill-Nerode ó l lema de l bombeamiento.

Eesiste dues aprossimaçones puramente algébricas que definen ua lenguaige regular. Se:

Σ ye un alfabeto fenito,
Σ* denota ua monoide libre subre Σ que ye cumpuosta por todas las cadeias formadas por Σ,
f : Σ* → M ye ua monoide homomórfica adonde M ye ua monoide fenita,
S ye un subconjunto de M

anton l cunjunto ye $\{w\in \Sigma ^{*}\,|\,f(w)\in S\}$ ye regular. To lenguaige regular surge dessa forma.

Se L ye un subconjunto de Σ*, define-se la seguinte relaçon d'eiquibaléncia de ~ (coincida cumo relaçon sintática) subre Σ*: u ~ b ye defenida por : uw ∈ L se i solamente se bw ∈ L para to w ∈ Σ*.

La lenguaige L ye regular se i solamente se l númaro de classes eiquibalentes de ~ ye fenita (Ua proba desso ye fornecida ne l'artigo de la monoide sintática); se esse ye l causo, esse númaro ye eigual al númaro de stados dun outómato fenito determinístico mínimo qu'aceita L.

Un cunjunto similar de declaraçones puode ser formulado por ua monoide $M\subset \Sigma ^{*}$ . Nesse causo, l'eiquibaléncia subre M lieba al cunceito dua lenguaige reconhecible.

Lenguaiges Finitas

Un subconjunto specífico de la classe de las lenguaiges regulares ye l cunjunto de las lenguaiges fenitas - aqueilhes que cunténen solo un númaro fenito de palabras. Essas lenguaiges son regulares, yá que ye possible criar ua spresson regular que ye la ounion de cada palabra de la lenguaige.

L númaro de palabras dua lenguaige regular

Para qualquiera lenguaige $L$ eisiste custantes $\lambda _{1},\,\ldots ,\,\lambda _{k}$ i polinómios $p_{1}(x),\,\ldots ,\,p_{k}(x)$ tal que para cada $m$ l númaro $s_{L}(m)$ de palabras de tamanho $m$ an $L$ sastifaç l'eiquaçon $s_{L}(m)=p_{1}(m)\lambda _{1}^{m}+\dotsb +p_{k}(m)\lambda _{k}^{m}$ . Assi, la nun regularidade d'alguas lenguaiges $L'$ puoden ser probadas pula enumeraçon de las palabras an $L'$ . Cunsidre, por eisemplo, la Lenguaige de Dyck de cadeias de parénteses balanceados. L númaro de palabras de tamanho $2n$ na lenguaige Dyck ye eigual al númaro Catalan $C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$ ,l qual nun ye de la forma $p(m)\lambda ^{m}$ , cumprobando la nun regularidade de la lenguaige de Dyck.

Teorema de l'iteraçon para lenguaiges regulares

Se L ye ua lenguaige regular, anton eisiste un m tal que para to x &esin; L tal que |x| ≥ m, x puode ser rescrito de la forma wyç, |y| ≤ m, i ∀ i, i ≥ 0 $xy^{i}z$ &esin; L

Beija tamien

Refréncias

Antrodution to the Theory of Cumputation. [S.l.]: PWS Publishing. 1997. ISBN 0-534-94728-X Chater 1: Regular Languages, pp.31–90. Susection "Decidable Porblems Cuncerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.

↑ M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-eiquipa hierarchy. Math. Systems Theory, 17:13–27, 1984.
↑ Cok, Stephen; Nguyen, Phuong (2010). Stephen, eid. Logical foundationes of prof cumplexity. Ithaca, NY: Association fur Symbolic Logic. 75 páiginas. ISBN 052151729X
↑ J. Hartmanis, P. L. Lewis II, and R. I. Stearnes. Hierarchies of memory-lemited cumputationes. Procedings of the 6th Annual IEEE Symposiun on Switching Circuit Theory and Logic Zeign, pp. 179–190. 1965.

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia Chomsky	Gramática	Linguagem	Reconhecedor
Tipo-0	Irrestrita	Recursivamente enumerável	Máquina de Turing
--	--	Recursiva	Máquina de Turing que sempre para
Tipo-1	Sensível ao contexto	Sensível ao contexto	Autômato linearmente limitado
Tipo-2	Livre de contexto	Livre de contexto	Autômato com pilha
Tipo-3	Regular	Regular	Autômato finito

[1] M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-eiquipa hierarchy. Math. Systems Theory, 17:13–27, 1984.

[2] Cok, Stephen; Nguyen, Phuong (2010). Stephen, eid. Logical foundationes of prof cumplexity. Ithaca, NY: Association fur Symbolic Logic. 75 páiginas. ISBN 052151729X

[3] J. Hartmanis, P. L. Lewis II, and R. I. Stearnes. Hierarchies of memory-lemited cumputationes. Procedings of the 6th Annual IEEE Symposiun on Switching Circuit Theory and Logic Zeign, pp. 179–190. 1965.

[1]

[2]

[3]