Taller gramaticas independientes del contexto

Taller gramáticas independientes del contexto.

1. Cree las gramáticas independientes del contexto para los siguientes lenguajes.
a. El conjuntode todas las cadenas de símbolos de 0 y 1 tales que todo 0 va seguido inmediatamente de al menos un 1.

S 1S| 01S|Є.

b. Las cadenas de símbolos oy 1 con un número igual de 0 y 1.

S 0S1|1S0|01S|10S|S01|S10| Є.

c. Las cadenas de 0 y 1 de la forma 00..0011..11 con número igual de 0 y 1.S 0S|1S|0R1|1R0|01R|10R|R01|R10| Є.
R0R|1R| Є.

d. Las cadenas de símbolos 0 y 1 de la forma 00..0011.11 con número igual de 0 y de 1.

S0S1| Є.

2. Dadas las siguientes gramáticas:

a. Quitar la recursividad por la izquierda de estas gramáticas.
b. Factorizar por la izquierda lasgramáticas.

2.1 R  R’|’ R El ‘|’ significa el operador “O” de las expresiones regulares.
R RR
R R*
R R+
R a|b

Sin recursividad por laizquierda
R aR’|bR’
R’ ’|’RR’|RR’|*R’|+R’| Є

No necesita factorizarse por la izquierda.

2.2 S  A | aBa | AbA
C  a A  Aa | Є
B  b B Bb |BC
A  aBaD |SBBb
C  CB | CA | b

Sin recursividad por la izquierda

S  aBaS’
S’ BBbS’|BBbbAS’| Є
C  aAC’|AaC’|bC’|C’
C’ BC’|AC’| ЄB bBB’
B’ bB’|CB’| Є
A aBaDA’|aBaBBbA’
A’ BBbA’|bABBbA’| Є

Factorizando la gramática por la izquierda

S  aBaS’
S’  BBbS’’| ЄS’’ S’|bAS’
C  aAC’|AaC’|bC’|C’
C’ BC’|AC’| Є
B bBB’
B’ bB’|CB’| Є
A aBaA’’
A’’ DA’|BBbA’
A’ BBbA’|bABBbA’| Є