Scribd
Cargar
328 vistas4 páginas

Expresiones Regulares y AFDs en Lenguajes Formales

El documento describe 8 lenguajes formales y pide diseñar autómatas finitos deterministas para cada uno. Los lenguajes incluyen cadenas sobre alfabetos binarios y ternarios que cumplen condiciones como comenzar y terminar con ciertos símbolos, tener un número par/impar de símbolos específicos, y no contener secuencias repetidas de símbolos. También se pide diseñar autómatas para lenguajes definidos por expresiones regulares dadas.

Cargado por

Arley Fiaga
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
328 vistas4 páginas

Expresiones Regulares y AFDs en Lenguajes Formales

El documento describe 8 lenguajes formales y pide diseñar autómatas finitos deterministas para cada uno. Los lenguajes incluyen cadenas sobre alfabetos binarios y ternarios que cumplen condiciones como comenzar y terminar con ciertos símbolos, tener un número par/impar de símbolos específicos, y no contener secuencias repetidas de símbolos. También se pide diseñar autómatas para lenguajes definidos por expresiones regulares dadas.

Cargado por

Arley Fiaga
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

Encontrar expresiones regulares para los lenguajes descritos a continuación:

(i) ∑ = {0,1, 2}. Lenguaje de todas las cadenas que comienzan con 2 y terminan con 1.
• 𝐿 = 2(0 ∪ 1 ∪ 2)1

(ii) ∑ = {a,b,e}.Lenguaje de todas las cadenas que tienen un número par de símbolos.
• 𝐿 = (𝑎 ∪ 𝑏 ∪ 𝑒)(𝑎𝑎 ∪ 𝑏𝑏 ∪ 𝑒𝑒 ∪ 𝑎𝑏 ∪ 𝑎𝑒 ∪ 𝑏𝑎 ∪ 𝑏𝑒 ∪ 𝑒𝑎 ∪ 𝑒𝑏)∗

(iii) ∑ = {a,b}.Lenguaje de todas las cadenas que tienen un número impar de símbolos .
• 𝐿 = 𝑏∗𝑎(𝑎𝑏∗𝑎 ∪ 𝑏)∗ ∪ 𝑎∗𝑏(𝑏𝑎∗𝑏 ∪ 𝑎)∗ .

(iv) ∑ = {a,b,e}.Lenguaje de todas las cadenas que tienen un número impar de símbolos.
• 𝐿 = 𝑏∗𝑎(𝑎𝑏∗𝑎 ∪ 𝑏)∗ ∪ 𝑎∗𝑏(𝑏𝑎∗𝑏 ∪ 𝑎)∗ ∪ 𝑎∗𝑐(𝑐𝑎∗𝑐 ∪ 𝑎)∗

(v) ∑ = {a,b}.Lenguaje de todas las cadenas que tienen un número impar de aes
• 𝐿 = 𝑏∗𝑎(𝑎𝑏∗𝑎 ∪ 𝑏)∗

(vi) ∑ = {a,b}.Lenguaje de todas las cadenas que tienen la cadena ab un número par de veces.
• 𝐿 = (𝑎+𝑏𝑏∗𝑎+𝑏 ∪ 𝑏)∗𝑎∗ ∪ 𝑎∗(𝑎𝑏𝑏∗𝑎𝑏)∗𝑎∗

(vii) ∑=
{a,b}. Lenguaje de todas las cadenas que tienen un número par de aes o un número impar de bes
• L = (𝑎𝑏∗𝑎 ∪ 𝑏)∗ ∪ 𝑎∗𝑏(𝑏𝑎∗ ∪ 𝑎)∗

(viii) ∑ = {0, 1,2}. 𝐿𝑒𝑛𝑔𝑢𝑎𝑗𝑒 𝑑𝑒 𝑡𝑜𝑑𝑎𝑠 𝑙𝑎𝑠 𝑐𝑎𝑑𝑒𝑛𝑎𝑠 𝑞𝑢𝑒 𝑛𝑜 𝑐𝑜𝑛𝑡𝑖𝑒𝑛𝑒𝑛 𝑑𝑜𝑠 𝑢𝑛𝑜𝑠 𝑐𝑜𝑛𝑠𝑒𝑐𝑢𝑡𝑖𝑣𝑜𝑠.

• 𝐿 = 0∗2∗(10+2+)∗ ∪ 0∗2∗1(0+2+1)∗

Diseñar autómatas finitos deterministas que acepten los siguientes lenguajes:

(i) ∑ = {O,1}. L = lenguaje de las cadenas sobre ∑ de longitud impar.


(ii) ∑ = {0,1}. L = lenguaje de las cadenas sobre ∑ que contienen un número impar de
unos.

(iii) ∑ = {a,b}.L = ab +

(iv) ∑ = {a,b}.L = ab ∗ U ab ∗ a

(v) ∑ = {O,1}. L = (O U 10) ∗

(vi) ∑ = {O,1}.L = (01 U 10) ∗


(vii) ∑ = {O, 1}.Lenguaje de todas las cadenas que no contienen dos unos consecutivos.

(viii) ∑ = {a,b}.L = lenguaje de las cadenas sobre ∑que contienen un número par de aes y un
número par de bes. Ayuda: utilizar 4 estados.

∑ = {a, b}. Para cada combinación de las condiciones "par" e "impar" y de las conectivas "o" e "y",
diseñar un AFD que acepte el lenguaje L definido por L = lenguaje de las cadenas con un número
par/impar de aes y/o un número par/impar de bes.

También podría gustarte