Que Es Un Lenguaje Regular PDF

Preview

Summary

Definición sobre qué es un Lenguaje Regular...

Description

LENGUAJES REGULARES -Un Lenguaje Regular es aquel que es generado por una Gramática Regular. -Un Lenguaje Regular es un Lenguaje Formal que puede ser definido por una Expresión Regular. -Un Lenguaje Regular es aquel que es reconocido por un Auntómata Finito. -Todo Lenguaje L que sera FINITO es un LR. -Las palabras que forma un Lenguaje Regular son una sucesión de simbolos concatenados que NO están relacionados entre sí. Ejemplo: El lenguaje L={an bn cn /n ≥ 1 } NO es un LR ya que los símbolos a,b y c estan relacionados entre sí mediante el coeficiente n. -En una palabra perteneciente a un LR es posible hacer que una parte intermedia de esa palabra se repita un número arbitrario de veces y que palabra resultante también pertenezca al mismo LR. Ejemplo: El lenguaje L={an / n es potencia positiva de 2 } NO es un LR ya que si tomo una parte intermedia de ,por ejemplo, la palabra a6 = “aaaaaa” = “a aaa aa” y repito 2 veces esa parte, obtengo: “a aaa aaa aa” = a9 , con n=9 ,como 9 no es una potencia positiva de 2, el lenguaje L NO es un LR. Lema de Bombeo: Se utiliza para demostrar que un Lenguaje NO es regular. No se puede utilizar para demostrar que un lenguaje SI es regular.

1

El “Lema de Bombeo” sólo se puede usar para probar que un lenguaje NO es un lenguaje regular (LR). No se puede usar para demostrar que un lenguaje SÍ es LR.

2

Ejemplo: Usando el “Lema de Bombeo” probar que el lenguaje L= {𝑎𝑛 𝑏𝑛 / 𝑛 ≥ 0} NO es un lenguaje regular (LR).

A simple vista se puede observar porque NO es un Lenguaje Regular (LR). Podemos tener una cantidad cualquiera de letras ´a´ pero luego debemos concatenarle la misma cantidad en letras ´b´. Por lo que, necesitamos guardar en un contador la cantidad de ‘a’ escritas para saber cuántas ‘b’ escribir después. Esto implica que el Autómata que reconoce este lenguaje debería ser capaz de recordar cuántas letras ´a´ se escribieron. Pero los Autómatas Finitos (AF) reconocedores de Lenguajes Regulares (LR) NO tienen memoria. Entonces, podemos afirmar que este lenguaje L NO es un LR.

Usando el “Lema de Bombeo”:

- Asumimos que L es un LR y elegimos una “longitud de bombeo” p=7

- Definimos una palabra S que pertenezca al lenguaje L. S = 𝑎𝑝 𝑏 𝑝

- Ahora, dividimos a S en tres partes: S=xyz

- Consideramos tres casos diferentes:

3

- Para el Caso 1: 1) Cumple con la condición nro1: |xy|= 6 < p 2) Cumple con la condición nro 2: |y|>0 3) Si tengo 𝑥 𝑦 𝑖 𝑧 con i igual a 2: 𝑥𝑦𝑦𝑧 aa aaaa aaaa abbbbbbb La palabra formada NO pertenece al lenguaje L. Por lo tanto, no cumple con la condición nro 3. - Para el Caso 2: 1) No cumple con la condición nro1: |xy|= 9 > p 2) Cumple con la condición nro 2: |y|>0 3) Si tengo 𝑥 𝑦 𝑖 𝑧 con i igual a 2: 𝑥𝑦𝑦𝑧 aaaaaaabb bbbb bbbb b La palabra formada tampoco pertenece al lenguaje L. Por lo tanto, no cumple con la condición nro 3. - Para el Caso 3: 1) No cumple con la condición nro1: |xy|= 8 > p 2) Cumple con la condición nro 2: |y|>0

4

3) Si tengo 𝑥 𝑦 𝑖 𝑧 con i igual a 2: 𝑥𝑦𝑦𝑧 aaaaa aabb aabb bbbbb La palabra formada tampoco pertenece al lenguaje L. Por lo tanto, no cumple con la condición nro 3.

Por lo tanto, demostramos que L= {𝒂𝒏 𝒃𝒏 / 𝒏 ≥ 𝟎} NO es un LR.

En cambio, si considero un número acotado de n: Por ejemplo: L= { 𝒂𝒏 𝒃𝒏 /𝟎 ≤ 𝒏 ≤ 𝟐 }

En este caso, se trata de un LR, ya que:

TODO LENGUAJE FINITO ES REGULAR Es por eso por lo que el lenguaje: L= { 𝒂𝒏𝒃𝒏 /𝟎 ≤ 𝒏 ≤ 𝟐 } = { Ɛ, 𝒂𝒃, 𝒂𝒂𝒃𝒃 } SÍ es un Lenguaje Regular.

5...