Diseñe Las Siguientes Expresiones Regulares, En Caso De Presentarse La Situación Explique Las Razones Por Las Que No Se Pueden Escribir Las Expresiones:

A. Desarrolle los siguientes ejercicios: (2 puntos)
1. Diseñe las siguientes expresiones regulares, en caso de presentarse la situación explique las razones por las que no se pueden escribir las expresiones:
a. Todas las cadenas de letras minúsculas que comiencen y finalicen con b.
ba*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*b

b. Todas las cadenas de dígitos que no contenganceros al principio.
(1+2+3+4+5+6+7+8+9) (0+1+2+3+4+5+6+7+8+9)*

c. El conjunto de cadenas formadas por {a, b, c} que contienen al menos una a y al menos una b.
c*b+c*a+ c* + c*a+c*b+ c*

d. El conjunto de todas las cadenas con dos ceros consecutivos (no necesariamente al final)
( + 1+0)*(00)+ ( + 1+0)*

2. Convierta en un AFD el AFN del ejercicio 2.3.2 de la página 56 del texto base.| 0 | 1 |
p | { q,s | { q |
*q | { r | { q,r |
r | { s | { p |
*s | | { p |

p
q
s
r
1
1
0
0
1
Tabla de transición para AFD.
0,1

0,1

Diagrama de transición

N=4; 2n =24 =16. Que son los estados del AFD.
| 0 | 1 |
p | { q,s | { q |
*q | { r | { q,r |
r | { s | { p |
*s | | { p |
*{ p,q | { q,r,s | { q,r |
{ p,r | { q,s | {p,q |
{ p,s | { q,s | { p,q |
*{ q,r | { r,s | { p,q,r |
*{ q,s | { r | { p,q,r |
*{ r,s | { s | { p |
*{ p,q,r | { q,r,s | { p,q,r |
*{ q,r,s | { r,s | { p,q,r |
*{ p,r,s | { q,s | { q,p |
*{ p,q,s | { q,r,s | { p,q,r |
*{ p,q,r,s | { q,r,s | { p,q,r |
| | |
| 0 | 1 |
P | X | Q |
*Q | R | W |
R | S | P |
*S | | P |
*T | B | W |
U |X | T |
*V | X | T |
*W | Y | A |
*X | R | A |
*Y | S | P |
*A | B | A |
*B | Y | A |
*C | X | T |
*D | B | A |
*E | B | A |
AFD.
P
Q
S
R
1
0
1
1
0
W
A
X
B
Y
0
1
1
0
0
1
1
1
0
0
1
1

3. Realice el ejercicio 2.5.2 sobre AFN – ε, de la página 68 del texto.
a) Calcule la clausura respecto de de cada uno de los estados.
| | a | b | c |
p | { q,r| | { q | { r |
q | | { p | { r | { p,q |
*r | | | | |

p
q
r
c
, b
a , c
b
, c

Clausura(P) = { p, q, r
Clausura(r) = { r
Clausura(q) = { q
b)
abc abb acc acb aab aac aaa aba bcc bca baa bac bcb cba cca cab caa cbb ccc cbc cac.
c)
d = ({p, q, r, b) = {q, r
d = ({p, q, r, a) = {p
d = ({p, q, r, c) = {p, q, r
d = ({q, r, a) ={p
d = ({q, r, b) = {r
d = ({q, r, c) = {p, q
d = ({p, a) = {p
d = ({p, b) = {q, r
d = ({p, c) = {p, q, r
d = ({p, q, a) = {p
d = ({p, q, b) = {q, r
b
d = ({ p,q , c) = {p,q,r
{ r

b
b
c
{q, r

c
b
a

a

a
{p,q
{p
{p,q,r

c

a

c

qo
q1
q2
0
,1
1
1
4. Convierta las siguientes expresiones regulares en un AFN con transiciones – ε.
a. 01*

qo
q1
q3
00

1
q2
q4
1
b. (0+1)01

qo
q1
0
0

q2
1
c. 00(0+1)*

B. Interacción con el Entorno Virtual de Aprendizaje (2 puntos)
Participe de los foros propuestos en el Entorno Virtual, usted debe trabajar lo siguiente:
Foro 1:
Mencione las razones por las cuales es necesario que realizar la eliminación de transiciones – ε en la construcción de autómatas.
*

Foro 2:Investigué y comente que es el análisis léxico y como trabajan las expresiones regulares dentro de este, explique cómo sería el funcionamiento de un analizador léxico dentro de un compilador.
* Un analizador léxico, también se le conoce como analizador lexográfico, es un programa diseñado para conformar una parte de un todo que es un compilador, recibe de entrada el código fuente, y produceuna salida conformada por tokens, que son componentes léxicos o símbolos.
* Estos tokens sirven para una posterior etapa del proceso de traducción, siendo la entrada para el analizador sintáctico, en ingles parser.
* Una expresión regular es una forma de representar a los lenguajes regulares finitos o infinitos, y se construye utilizando caracteres del alfabeto sobre el cual se define...