Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1234 ou 1212 ou 3434 como prefixo, 3412 ou 4421 ou 1243 ou 2234 como subpalavra e 2212 ou 1123 ou 2431 ou 3444 como sufixo}.

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {1, 2, 3, 4}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   123412212
                 |   123412431
                 |   343412212
                 |   343412431
                 |   1234421123
                 |   3434421123
                 |   1212431
                 |   121243444
                 |   121223444
     < pre >     ->  1234
                 |   1212
                 |   3434
     < presub >  ->  123412
                 |   1234421
                 |   121243
                 |   1212234
                 |   343412
                 |   3434421
     < sub >     ->  3412
                 |   4421
                 |   1243
                 |   2234
     < subsuf >  ->  3412212
                 |   3412431
                 |   4421123
                 |   12431
                 |   1243444
                 |   223444
     < suf >     ->  2212 
                 |   1123
                 |   2431
                 |   3444
     < alf >     ->  < alf > 1
                 |   < alf > 2
                 |   < alf > 3
                 |   < alf > 4
                 |   ε  }

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {1, 2, 3, 4}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   123412212
                 |   123412431
                 |   343412212
                 |   343412431
                 |   1234421123
                 |   3434421123
                 |   1212431
                 |   121243444
                 |   121223444
     < pre >     ->  1234
                 |   1212
                 |   3434
     < presub >  ->  123412
                 |   1234421
                 |   121243
                 |   1212234
                 |   343412
                 |   3434421
     < sub >     ->  3412
                 |   4421
                 |   1243
                 |   2234
     < subsuf >  ->  3412212
                 |   3412431
                 |   4421123
                 |   12431
                 |   1243444
                 |   223444
     < suf >     ->  2212 
                 |   1123
                 |   2431
                 |   3444
     < alf >     ->  1 < alf >
                 |   2 < alf >
                 |   3 < alf >
                 |   4 < alf >
                 |   ε  }