Bom vejamos que o Linguagem L aceita seguindo a premissa:
{a,b,c,d}
- assim temos que os únicos caracteres presentes na linguagem são a,b,c,d
*
- todas as possíveis palavras que podem ser formadas por estes caracteres
Mas há uma regra :
p does not contains subsequence bbab
- Ou seja a palavra não pode conter a sequência bbab
Ambas máquinas de estados e gramática regular estão corretas, contudo quando você for montar a REGEX você pode ter em mente que apenas dando match em bbab
já torna a sequência inválida.
Usando o JFlap montei o autômato finito na qual podemos analisar melhor
Gramática Regular
Se a linguagem que você está usando já possui as alternativas look-ahead, torna-se simples montas uma validação por REGEX.
(?=^[abcd]*$)(?!^.*bbab.*$).*
(?=^[abcd]*$)
- vai aceitar apenas os caracteres envolvidos
(?!^.*bbab.*$)
- se encontrar em qualquer parte da sentença atual bbab
ira recusar o match.
Veja mais no debug
Agora que estiver montando em REGEX pura, que não possui look-ahead torna-se um pouco complexo montar a regex, pois o processo é baseado em aceitação e não negação ou seja sua sentença deve iniciar e ir batendo todos os estados possíveis ate chegar no fim da sentença, se qualquer estado não for cumprido então não gera match.
Seguindo a REGEX proposta pelo @Miguel:
^($|[^b]|b($|[^b]|b(b)*($|[^ab]|a($|[^b]))))*$
Esta se baseia em dar match positivo se baseando por inicio(^
) e fim($
) da sentença.
Questões
- É verdade que o regex é computacionalmente equivalente a gramáticas regulares? Ou gramáticas regulares é um super-conjunto próprio?
Na verdade elas tem relação, pois podem ser geradas por um AFD (Autômato Finito Determinístico), contudo, como você pode ver na imagem abaixo, elas não possuem uma relação direta.
Fonte : Expressões Regulares e Gramáticas Regulares
Se você tiver uma ER ou GR e converter para AFε - o que não é muito complicado já que o ε
(movimento vazio) te deixa pular de uma transição pra outra sem problemas - não quer disser que você vai conseguir completar as demais conversões de AFε -> AFN -> AFD
já que a cada passo você esta restringindo regras e dependendo da complexidade não sera possível realizar a conversão.
Em algumas fontes que encontrei é dito que REGEX se baseia em RLG (Gramática Linear a Direita(Right)) ou LLG (Gramática Linear a Esquerda (Left)), geralmente RLG. link
Mas na verdade é implícito, pois essas conversões serão possíveis.
- Qual algoritmo posso usar para transformar o meu AFD em regex?
Primeiramente converta-o para uma RLG, e após aplique esta regra :
Original : Steps to convert regular expressions directly to regular grammars and vice versa
- Qual a expressão regular (matematicamente falando) que reconhece
L
?
Vou ficar devendo.
Adendo
Autômatos Finitos Determinísticos e Não Determinísticos
bbab
deve retornar falso, portanto a gramática não pode produzir essa subpalavra de jeito algum. Olha na máquina de estados que, quando é produzida essa palavra, vai no estado além da salvaçãodamnation
, a partir do qual não consegui ir para um estado de aceitaçãoqa
, porque está voltando para o início ao ler[^a]
? Não deveria ser[^b]
?^($|[^b]|b($|[^b]|b(b)*($|[^ab]|a($|[^b]))))*$
... é o melhor que consegui! =D