Descriu l'algoritme per analitzar una gramàtica sense context i la seva complexitat temporal.
L'anàlisi d'una gramàtica sense context implica analitzar una seqüència de símbols segons un conjunt de regles de producció definides per la gramàtica. Aquest procés és fonamental en diverses àrees de la informàtica, inclosa la ciberseguretat, ja que ens permet entendre i manipular dades estructurades. En aquesta resposta, descriurem l'algorisme per analitzar una gramàtica sense context i discutirem la seva complexitat temporal.
L'algoritme més utilitzat per analitzar gramàtiques sense context és l'algoritme CYK, que porta el nom dels seus inventors Cocke, Younger i Kasami. Aquest algorisme es basa en la programació dinàmica i funciona segons el principi de l'anàlisi de baix a dalt. Construeix una taula d'anàlisi que representa totes les anàlisis possibles per a subcadenes de l'entrada.
L'algorisme CYK funciona de la següent manera:
1. Inicieu una taula d'anàlisi amb dimensions nxn, on n és la longitud de la cadena d'entrada.
2. Per a cada símbol de terminal de la cadena d'entrada, ompliu la cel·la corresponent de la taula d'anàlisi amb els símbols no terminals que el produeixen.
3. Per a cada longitud de subcadena l de 2 a n, i cada posició inicial i d'1 a n-l+1, feu el següent:
a. Per a cada punt de partició p de i a i+l-2, i cada regla de producció A -> BC, comproveu si les cel·les (i, p) i (p+1, i+l-1) contenen símbols no terminals B i C , respectivament. Si és així, afegiu A a la cel·la (i, i+l-1).
4. Si el símbol inicial de la gramàtica està present a la cel·la (1, n), la cadena d'entrada es pot derivar de la gramàtica. En cas contrari, no pot.
La complexitat temporal de l'algorisme CYK és O(n^3 * |G|), on n és la longitud de la cadena d'entrada i |G| és la mida de la gramàtica. Aquesta complexitat sorgeix dels bucles imbricats utilitzats per omplir la taula d'anàlisi. L'algorisme examina tots els punts de partició possibles i les regles de producció per a cada longitud de subcadena, donant lloc a una complexitat de temps cúbic.
Per il·lustrar l'algorisme, tingueu en compte la següent gramàtica sense context:
S -> AB | BC
A -> AA | a
B -> AB | b
C -> BC | c
I la cadena d'entrada "abc". La taula d'anàlisi d'aquest exemple seria el següent:
| 1 | 2 | 3 |
——-|—–|—–|—–|
1 | A,S | B,C | S |
——-|—–|—–|—–|
2 | | B,C | A |
——-|—–|—–|—–|
3 | | | C |
——-|—–|—–|—–|
En aquesta taula, la cel·la (1, 3) conté el símbol d'inici S, que indica que la cadena d'entrada "abc" es pot derivar de la gramàtica donada.
L'algorisme per analitzar una gramàtica sense context, com l'algoritme CYK, ens permet analitzar i entendre dades estructurades. Funciona construint una taula d'anàlisi i comprovant les derivacions vàlides segons les regles de producció de la gramàtica. La complexitat temporal de l'algorisme CYK és O(n^3 * |G|), on n és la longitud de la cadena d'entrada i |G| és la mida de la gramàtica.
Altres preguntes i respostes recents sobre Complexitat:
- La classe PSPACE no és igual a la classe EXPSPACE?
- La classe de complexitat P és un subconjunt de la classe PSPACE?
- Podem demostrar que les classes Np i P són iguals trobant una solució polinomial eficient per a qualsevol problema NP complet en un TM determinista?
- La classe NP pot ser igual a la classe EXPTIME?
- Hi ha problemes a PSPACE per als quals no es coneix l'algorisme NP?
- Un problema SAT pot ser un problema NP complet?
- Pot un problema estar en classe de complexitat NP si hi ha una màquina de tornejat no determinista que el resolgui en temps polinomial
- NP és la classe de llenguatges que tenen verificadors de temps polinomials
- P i NP són realment la mateixa classe de complexitat?
- És cada llenguatge lliure de context a la classe de complexitat P?
Veure més preguntes i respostes a Complexity