Ejercicios de La Unidad 3 Teoria de La Computacion

Secretaría de

Educación Pública

Del Estado de Puebla

INSTITUTO TECNOLÓGICO SUPERIOR DE SAN MARTÍN TEXMELUCAN

Organismo Público Descentralizado del Gobierno del Estado

INSTITUTO TECNOLOGICO SUPERIOR DE SAN MARTIN TEXMELUCAN.

TEORIA DE LA COMPUTACION

PROFESORA: YESENIA PEREZ REYES.

EJERCICIOS UNIDAD III

JUAN CARLOS CUAPIO TEYSSIER

Secretaría de

Educación Pública



Organismo Público Descentralizado del Gobierno del Estado Ejercicios de Teoría de la Computación

Unidad 3

1.- Cada nombre y apellido debe comenzar por mayúscula.Gramaticanombre --->nom nom2 esp nom nom2nom2---> esp nom | εnom---> nom min | maymay--->A|B|C|D|....|Zmin---->a| b |c |d|...|zesp--->" "

¿Determine cuales son los elementos No terminales?N= {nombre, nom2, nom, may, min, esp}

¿Determinar cuales son los elementos Terminales?T= {A, B,....Z, a, b,...z," ", ε}

¿Cual es el simbolo inicial?S={nom}

Derivar por la izquierda para obtener tu nombre con apellidos y el de otra persona que tenga dos nombres y sus apellidos.Realizar los arboles de Derivación.

Generar: Juan Carlos Cuapio Teyssier

nombre nom nom2 esp nom nom2 nombre nom min nom2 esp nom nom2 nombre nom min min nom2 esp nom nom2 nombre nom min min min nom2 esp nom nom2 nombre nom min min min nom2 esp nom nom2 nombre nom min min min nom2 esp nom nom2 nombre may min min min nom2 esp nom nom2 nombre J min min min nom2 esp nom nom2

Secretaría de

Educación Pública



Organismo Público Descentralizado del Gobierno del Estado nombre Ju min min nom2 esp nom nom2

nombre Jua min nom2 esp nom nom2 nombre Juan nom2 esp nom nom2 nombre Juan nom esp nom nom2

nombre Juan nom min esp nom nom2 nombre Juan nom min min esp nom nom2 nombre Juan nom min min min esp nom nom2 nombre Juan nom min min min min esp nom nom2 nombre Juan may min min min min min esp nom nom2 nombre Juan C min min min min min esp nom nom2 nombre Juan Ca min min min min esp nom nom2 nombre Juan Car min min min esp nom nom2 nombre Juan Carl min min esp nom nom2 nombre Juan Carlo min esp nom nom2 nombre Juan Carlos esp nom nom2 nombre Juan Carlos nom min nom2 nombre Juan Carlos nom min min nom2 nombre Juan Carlos nom min min min nom2 nombre Juan Carlos nom min min min min nom2 nombre Juan Carlos nom min min min min min nom2 nombre Juan Carlos may min min min min min nom2nombre Juan Carlos C min min min min min nom2 nombre Juan Carlos Cu min min min min nom2 nombre Juan Carlos Cua min min min nom2 nombre Juan Carlos Cuap min min nom2 nombre Juan Carlos Cuapi min nom2 nombre Juan Carlos Cuapio nom2 nombre Juan Carlos Cuapio esp nom nombre Juan Carlos Cuapio nom nombre Juan Carlos Cuapio nom min nombre Juan Carlos Cuapio nom min min

nombre Juan Carlos Cuapio nom min min min nombre Juan Carlos Cuapio nom min min min min nombre Juan Carlos Cuapio nom min min min min min nombre Juan Carlos Cuapio nom min min min min min min nombre Juan Carlos Cuapio nom min min min min min min min nombre Juan Carlos Cuapio may min min min min min min min nombre Juan Carlos Cuapio T min min min min min min minnombre Juan Carlos Cuapio Te min min min min min min nombre Juan Carlos Cuapio Tey min min min min min

Secretaría de

Educación Pública



Organismo Público Descentralizado del Gobierno del Estado nombre Juan Carlos Cuapio Teys min min min min

nombre Juan Carlos Cuapio Teyss min min min nombre Juan Carlos Cuapio Teyssi min min nombre Juan Carlos Cuapio Teyssie min

nombre Juan Carlos Cuapio Teyssier min nombre Juan Carlos Cuapio Teyssier

Secretaría de

Educación Pública




nom

nom

nom

nom

may

s

min l

may

min

a

r

min omin

n

u

J

min

min

min

min

nom

a

C

nom

nom

nom

nom

nom

may

nom

nom

nom

nombre

min

min

min

min

o

C

u

i

a

p

nom

min

nom

nom

nom

nom

nom

nom

nom

may

min

min

min

min

min

min

min

r

e

i

s

s

y

e

T

Nom2Nom1Nom2m

espp

Secretaría de

Educación Pública




Generar: Yesenia Pérez Reyes

nombre nom esp nom nom2 nombre nom min esp nom nom2 nombre nom min min esp nom nom2 nombre nom min min min esp nom nom2 nombre nom min min min min esp nom nom2 nombre nom min min min min min esp nom nom2 nombre nom min min min min min min esp nom nom2 nombre may min min min min min min esp nom nom2 nombre Y min min min min min min esp nom nom2 nombre Ye min min min min min esp nom nom2 nombre Yes min min min min esp nom nom2 nombre Yese min min min esp nom nom2 nombre Yesen min min esp nom nom2 nombre Yeseni min esp nom nom2 nombre Yesenia esp nom nom2 nombre Yesenia nom min nom2 nombre Yesenia nom min min nom2 nombre Yesenia nom min min min nom2 nombre Yesenia nom min min min min nom2 nombre Yesenia may min min min min nom2 nombre Yesenia P min min min min nom2 nombre Yesenia Pé min min min nom2 nombre Yesenia Pér min min nom2 nombre Yesenia Pére min nom2 nombre Yesenia Pérez nom2 nombre Yesenia Pérez esp nom nombre Yesenia Pérez nom min nombre Yesenia Pérez nom min min nombre Yesenia Pérez nom min min min nombre Yesenia Pérez nom min min min min

Secretaría de

Educación Pública




nombre Yesenia Pérez may min min min min nombre Yesenia Pérez R min min min min nombre Yesenia Pérez Re min min min nombre Yesenia Pérez Rey min min nombre Yesenia Pérez Reye min nombre Yesenia Pérez Reyes

nom

nom

nom

nom

nom

nom

nombre

min

Nom2

Nom 3

nom

min s

esp

nom

min e

minnom y

ᵋ

min

min

min

min

min

i

a

e

R

n

e

s

nom

may

esp

nom

nom

nom

may

min

min

min

min

nom z

e

r

e

P

enom

may

min

Y

ᵋᵋ

Secretaría de

Educación Pública




2. Sea la Gramática.

S (L) | aL L, S | S

¿Determinar cuáles son los elementos NO TERMINALES?N= {S, L}Determinar cuáles son los elementos TERMINALES?T= {a}¿Cuál es el símbolo inicial?S= {(L)}Generar los siguientes lenguajes derivando por la izquierda y por la derecha.(a, a)(a, (a, a))(a, ((a, a), (a, a)))Realizar los árboles de derivaciónPOR LA IZQUIERDA:(a, a)

Lenguaje Generado

Árbol

S(L)S (L, S)S (S, S)S (a, S)S (a, a)

Secretaría de

Educación Pública




(a, (a, a))

Lenguaje Generado

Árbol

S(L)S (L, S)S (S, S)S (a, S)S (a, (L))S (a, (L,

S))S (a, (S,

S))S (a, (a,

S))S (a, (a,

a))

Secretaría de

Educación Pública




(a, ((a, a), (a, a)))

Lenguaje Generado

Árbol

S(L)S (L, S)S (S, S)S (a, S)S (a, (L))S (a, (L, S))S (a, (S, S))S (a, ((L), S))S (a, ((L, S),

S))S (a, ((S, S),

S))S (a, ((a, S),

S))S (a, ((a, a),

S))S (a, ((a, a),

(L)))S (a, ((a, a),

(L,S)))S (a, ((a, a),

(S,S)))S (a, ((a, a),

(a,S)))S (a, ((a, a),

(a,a)))

Secretaría de

Educación Pública




POR LA DERECHA:

(a, a)

Lenguaje Generado

S(L)S (L, S)S (L, a)S (S, a)S (a, a)

Árbol

Secretaría de

Educación Pública




(a, (a, a))

Lenguaje Generado

Árbol

S(L)S (L, S)S (L, (L))S (L,(L, S))S (L, (L,

a))S (L, (S,

a))S (L, (a,

a))S (S, (a,

a))S (a, (a,

a))

Secretaría de

Educación Pública




(a, ((a, a), (a, a)))

Lenguaje Generado

Árbol

S(L)S (L, S)S (L, (L))S (L, (L, S))S (L, (L, (L)))S (L, (L, (L,

S)))S (L, (L, (L,

a)))S (L, (L, (S,

a)))S (L, (L, (a,

a)))S (L, (S, (a,

a)))S (L, ((L), (a,

a)))S (L, ((L, S),

(a,a)))S (L, ((L, a),

(a,a)))S (L, ((S, a),

(a,a)))S (L, ((a, a),

(a,a)))S (S, ((a, a),

(a,a)))S (a, ((a, a),

(a,a)))

Secretaría de

Educación Pública




3. Sean las siguientes Gramáticas pasarlas a su forma normal de Chomsky:

Gramatica 1

S--> zMzM--> NM--> yMyN--> x

Eliminando los no generadores


Eliminando simbolos no alcanzables


Eliminando producciones ε

S--> zMzM--> N

Gramatica 2

S --> xSy S --> wNz N --> s


S --> xSy S --> wNz N --> s


S --> xSy S --> wNz N --> s

Eliminando producciones ε

S --> xSy S --> wNz N --> s

Eliminando producciones

Gramatica 3

S --> aNaN --> M N --> bNb M --> x


S --> aNaN --> M N --> bNb M --> x


S --> aNaN --> M N --> bNb M --> x

Eliminando producciones ε S --> aNaN --> M

S zMzM NM yMyN x

S xSyS wNzN s

S aNaN MN bNbM x

Secretaría de

Educación Pública



Organismo Público Descentralizado del Gobierno del Estado M-->

yMy

N--> x

Eliminando producciones Unitarias.S--> zMzM--> xM--> yMyN--> x

Reemplazar terminales por variables

S--> C1MC1M--> A1M--> B1MB1N--> A1A1-->xB1-->yC1-->z

Reemplazar producciones con tres o mas variables

S--> C1Y1M--> A1M--> B1Y2N--> A1A1-->xB1-->yC1-->z

Y1--->M1C1Y2--->MB1

Unitarias

S --> xSy S --> wNz N --> s


S --> A1SB1S --> D1NC1 N --> E1A1 --> xB1 --> yC1 --> zD1 --> wE1 --> s


S --> A1Y1 S --> D1Y2 N --> E1A1 --> xB1 --> yC1 --> zD1 --> wE1 --> s

Y1 --> SB1Y2 --> NC1

N --> bNb

M --> x Eliminando producciones Unitarias S --> aNaN --> x N --> bNb M --> x


S --> A1NA1N --> C1 N --> B1NB1 M --> C1 A1 --> aB1 --> bC1 --> x


S --> A1Y1N --> C1 N --> B1Y2 M --> C1 A1 --> aB1 --> bC1 --> x

Y1 --> NA1Y2 --> NB1

Secretaría de

Educación Pública




4. Hacer una gramática independiente del contexto (G. I. C.), que genere la sentencia condicional if con las siguientes restricciones:

Siempre se va a comparar una variable con un número entero o una variable con otra variable.

Los operadores relacionales son: < | > | ≤ | ≥ | == | != Las variables deben empezar en una letra y después de esa

letra pueden haber cualquier cantidad de números o letras. Los números solamente van a ser enteros de cualquier

cantidad de dígitos. Un número no debe empezar en cero, pero puede ser cero. Se pueden utilizar los operadores lógicos && (and) y || (or). Solamente se van a utilizar los paréntesis después de if y al

final del if.

Nota: Este problema no se vio en clase.

5. Dada la siguiente gramática, eliminar la ambigüedad, factor izando términos comunes izquierdos y recursividad izquierda.S EE E + F | E – F | FF F * L | F / L | LL (E) | num | id

Eliminación por factor común izquierdo

S E

E FE´

E´ +E|E-|E

F F´|L

F´ *F| F/| E

L (E) |num|id

Secretaría de

Educación Pública




Eliminación de recursividad por la izquierda

S E

E E´+F|E´-F|F

E´ E

F F´*L|F´/L|L

F´ F

L (E) |num |id

Documents

Ejercicios de La Unidad 3 Teoria de La Computacion