DATOS¶

DANIEL EDUARDO BAUTISTA FUENTES 2121323

EJERCICIOS GRAMÁTICAS

1. a+b+¶

Gramática¶

S ->  a S
    | L
L ->  b L
    | M
M ->  b

ej. aab¶

S -> a S        :   aS
S -> a S        :   aaS
S -> L          :   aaL
L -> M          :   aaM
M -> b          :   aab

2. Numeros binarios¶

Gramática¶

S ->  L S
    | λ
L ->  1
    | 0

ej. 1001¶

S -> LS         : LS
L -> 1          : 1S
S -> LS         : 1LS
L -> 0          : 10S
S -> LS         : 10LS
L -> 0          : 100S
S -> LS         : 100LS
L -> 1          : 1001S
S -> λ          : 1001

3. cadenas binarias que contienen exactamente 2 1¶

Gramática¶

0* 1 0 * 1 0 *

S ->  C 1 C 1 C
C ->  0 C
    | 0
    | λ

ej 11000¶

S ->    C 1 C 1 C   : C1C1C
C ->    λ       : λ1C1C = 1C1C
C ->    λ       : 1λ1C  = 11C
C ->    0 C     : 110C
C ->    0 C     : 1100C
C ->    0       : 11000

4. cadenas de la forma: aibi tal que i >= 0 ?¶

NOTA: no entiendo si se refiere a a i b i o a la cadena tal cual como si la sentencia de progra fuera Asi que colocaré ambas

FORMA ai*bi*¶

Gramática¶

S ->  a L b L
L ->  i L
    | i
    | λ

ej. aiiibi¶

S -> a L b L        : aLbL
L -> i L        : aiLbL
L -> i L        : aiiLbL
L -> i L        : aiiiLbL
L -> λ          : aiiiλbL = aiiibL
L -> i          : aiiibi

FORMA aibi tal que i >= 0¶

Gramática¶

S ->    aibi T_Q ASG
T_Q ->  tal que
ASG ->  i >= 0

ej. aibi tal que i >= 0¶

S   -> aibi T_Q ASG     : aibi T_Q ASG
T_Q -> tal que          : aibi tal que ASG
ASG -> i >= 0           : aibi tal que i >= 0

5. Cadenas (ab|ba)*¶

Gramática¶

L ->      AQ L
L ->      AQ
L ->      λ

AQ ->     ab
        | ba

ej. babaab¶

L  -> AQ L      : AQ L
AQ -> ba        : baL
L  -> AQ L      : baAQL
AQ -> ba        : babaL
L  -> AQ        : babaAQ
AQ -> ab        : babaab