23

O @LINQ me desafiou a escrever uma expressão regular para reconhecer a seguinte linguagem L:

Linguagem sobre o alfabeto desejado {a,b,c,d}, qualquer palavra que não contenha a subexpressão "bbab"

Consegui montar, sobre essa premissa, a seguinte máquina de estados finito:

Máquina de estados finito para reconhecer a palavra que não contém "bbab"

o Miguel Angelo detectou um erro de digitação no AFD descrito originalmente. A transição qa ->q0 se dá no caso [^b], conforme figura nova; na figura antiga com [^a] estava errado

E, também, a seguinte gramática regular (recursão de cauda):

L(G) = L, gramática sobre {a,b,c,d} que gera a L do desafio

Já estou com essas informações em mãos, mas não estou conseguindo escrever uma expressão regular para detectar L. Então tenho os seguintes questionamentos:

  • Qual a expressão regular (matematicamente falando) que reconhece L?
  • É verdade que o regex é computacionalmente equivalente a gramáticas regulares? Ou gramáticas regulares é um super-conjunto próprio?
  • Qual algoritmo posso usar para transformar o meu AFD em regex?
  • Qual algoritmo posso usar para transformar minha gramática regular determinística em regex?
14
  • @GuilhermeLautert AFD: autômato finito determinístico Commented 28/09/2017 às 12:32
  • @GuilhermeLautert conter 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ção damnation, a partir do qual não consegui ir para um estado de aceitação Commented 28/09/2017 às 12:34
  • 1
    Vamos continuar esta discussão no chat. Commented 28/09/2017 às 12:38
  • 1
    Na última parte da máquina, no estado qa, porque está voltando para o início ao ler [^a]? Não deveria ser [^b]? Commented 1/10/2017 às 1:42
  • 2
    Consegui chegar nessa expressão, a partir da sua AFD: ^($|[^b]|b($|[^b]|b(b)*($|[^ab]|a($|[^b]))))*$... é o melhor que consegui! =D Commented 1/10/2017 às 3:00

1 Resposta 1

18
+100

Bom vejamos que o Linguagem L aceita seguindo a premissa:

inserir a descrição da imagem aqui

  • {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.

inserir a descrição da imagem aqui

Usando o JFlap montei o autômato finito na qual podemos analisar melhor

inserir a descrição da imagem aqui

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.

inserir a descrição da imagem aqui

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 :

inserir a descrição da imagem aqui

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

1
  • 1
    Com símbolos de começo e fim eu creio que seja válido matematicamente também. Para mim me atendeu perfeitamente Commented 6/10/2017 às 14:21

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .