Gramáticas Incontextuales

Thanat0s

Vale, creo que he conseguido solucionarlo! :o

Aunque está un poco chapuza porque hay algunos casos que se repiten y se pueden solucionar por derivaciones distintas y tal, pero bueno, al menos está solucionado.
Si alguien le encuentra alguna pega que lo diga pls.

I -> A' | B' | C' | S'C | AS'' | S'''

(estos serían los casos bases en los que hay dos letras del alfabeto pero falta la otra)
A' -> aA'b | € | A | B
B' -> bB'c | € | B | C
C' -> aC'c | € | A | C

(los casos complejos)
S' -> aS'b | A | B
S'' -> bS''c | B | C
S''' -> aS'''c | B'' | B'''
B'' -> bB'' | bcc
B''' -> B'''b | aab

Y los casos más elementales:
A -> aA | a
B -> bB | b
C -> cC | c

Al final, partiendo de la base de que se pueden repetir el número de dos de las letras se consigue sacar, ya que la restricción es menos fuerte que partiendo de que ningún número de letras puede ser el mismo.

Edit: se podría simplificar y dejarlo en FNC (forma normal de Chomsky) pero paso, no me lo piden xD

TBT

I -> A' -> A-> "a", estás generando palabras q no son del lenguaje.
El € es lambda, no? También la puedes obtener xd

Thanat0s

La a, b y c si que serían parte del lenguaje, lo del epsilon o lambda si que es verdad que sobra.

B

Porque no llegué antes sino te lo hubiera solucionado en un momentito... :clint:

6 meses después
aldarius

Mentes preclaras del foro, a ver si sacais este:

L = {ai b2n cj | n>=0 & j > 3i > 0}

Ya digo de entrada que no me aclaro con este proceso de bucle que tienen las gramáticas incontextuales, pero este era mi "borrador":

S → acccc | abbcccc
A → aAcccC
B → AbbBC

En principio no le veo problema en A o B, el problema es que si pongo S -> A | B es posible que acepte "accc" (escoge A inicialmente i como no hay A o C aún...), y el nombre de c's tiene que ser superior al triple de a's que haya.

Que por cierto, en los apuntes de la materia tengo el del inicio del hilo resuelto pero con n > 0, no con n >= 0.

Ahora que lo pienso... si se pone una parte derecha sin variables (las letras mayúsculas) se sobreentiende que puede ser el valor inicial. ¿Esto es muy descabellado?

S → A | B
A → aAcccC |acccc
B → AbbBC | abbcccc

1 respuesta
W

Inferencia, inferencia everywhere..es bastante sencillo.

aldarius

He editado mi post, a lo mejor en 5 minutos he conseguido ver lo que no he visto en toda una tarde delante del ordenador ¬¬

aldarius

Me olvidaba de la variable C, que no tiene que ser justamente una unidad superior a las a's, por lo que puedo añadir c's a doquier:

S → A | B
A → aAcccC | acccc | C
B → AbbBC | abbcccc | C
C → AcC | ABcC

12 meses después
D

#35 Esta puede ser una solucion a tu problema
S-> aSccc | aBcccC
B-> λ | bbB
C-> cC | c

Ahora propongo yo otro problema

L={w#w' | w,w' E (a+b+c)* & wR es una subpalabra de w'}

Usuarios habituales