Lenguaiges regulares

De Biquipédia
Saltar pa: nabegaçon, percura

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[eiditar | editar código-fonte]

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 LaB (ounion), LaB (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^nb^n\,\vert\; n\ge 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[eiditar | editar código-fonte]

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

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


Resultados subre la Cumplexidade[eiditar | editar código-fonte]

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). REGULARAC0, 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á naAC0.[1] An cuntrapartida, REGULAR nun cuntén AC0, 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 AC0.[2]

Se ua lenguaige ye 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[eiditar | editar código-fonte]

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:


Decidindo se ua lenguaige ye regular[eiditar | editar código-fonte]

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 : uwL se i solamente se bwL 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[eiditar | editar código-fonte]

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[eiditar | editar código-fonte]

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[eiditar | editar código-fonte]

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[eiditar | editar código-fonte]


Refréncias[eiditar | editar código-fonte]

Modelo:Main otherModelo:Category handler/numbered

  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. In: Stephen. Logical foundationes of prof cumplexity. Ithaca, NY: Association fur Symbolic Logic, 2010. 75 p. 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.


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