[Cascavel-pm] Quando usar Gramatica e quando usar Regexp? [Was: Artigo - Como Perl Salvou o Projeto Genoma]

[Wendel Scardua]

 A string "a^n b^n" (que não é regular) não pode ser reconhecida com uma
regexp do Perl (a menos de trapaças envolvendo "use re 'eval'").

a^n b^n = "", "ab", "aabb", "aaabbb", etc... , mas não "aabbbb", nem "aaab",
etc.
Essa linguagem (i.e. conjunto de strings) não é "regular", mas sim, "livre
de contexto". Logo, é reconhecida por um autômato-a-pilha, ou por uma
gramática livre de contexto:

S = [vazio] | aSb

Outro exemplo são strings de "(" e ")" balanceados: "()", "(()()(()))",
etc... Não dá pra fazer uma regexp que reconheça isso. Acho que a gramática
correspondente é:

S = [vazio] | (S)S

Em resumo, cuidado: a palavra regular pode não significar o que você acha
que ela significa :-)

On 5/24/07, Luis Motta Campos <luismottacampos em yahoo.co.uk> wrote:
>
> > Mas se a sua string, mesmo que seja uma linha, tiver muitas variações
> > -- poderíamos dizer, se ela for mais ou menos "irregular" -- nesse
> > caso uma gramática pode ajudar bastante.
>
>    Sem querer forçar a amizade, você pode por favor me dar um exemplo?
>
>    Putamplexos!
>

-- 
[]s
Wendel

"Não ajustar o auto-ajuste" - http://wendel.scardua.net/
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: http://mail.pm.org/pipermail/cascavel-pm/attachments/20070524/ebfed2f2/attachment.html