Como provar que um idioma é regular?

48

Existem muitos métodos para provar que um idioma não é regular , mas o que preciso fazer para provar que um idioma é regular?

Por exemplo, se me é dado que é regular, como posso provar que o a seguir também é regular?LL

L:={wL:uv=w for uΣL and vΣ+}

Posso desenhar um autômato finito não determinístico para provar isso?

corium
fonte
1
há um erro de digitação na definição do seu , edite para corrigir. L
Ran G.
2
"Desenho" não é prova; você precisa fornecer uma NFA e provar que aceita o idioma.
Raphael
Eu acho que a definição da linguagem ainda não faz sentido ...
hugomg
2
de qualquer forma, o idioma específico é irrelevante se a pergunta for "posso desenhar um NFA para provar que é regular". @corium, podemos editar a pergunta para refletir a pergunta mais geral: "como provar que um específico é regular"? L
Ran G.

Respostas:

48

Sim, se você puder criar um dos seguintes:

para alguma língua , então é regular. Existem modelos mais equivalentes , mas os itens acima são os mais comuns.LLL

Também existem propriedades úteis fora do mundo "computacional". também é regular seL

  • é finito,
  • você pode construí-lo executando determinadas operações em idiomas regulares e essas operações são fechadas para idiomas regulares , como

    • interseção,
    • complemento,
    • homomorfismo,
    • reversão,
    • quociente esquerdo ou direito,
    • transdução regular

    e mais , ou

  • usando o teorema de Myhill – Nerode se o número de classes de equivalência para for finito.L

No exemplo dado, temos alguns idiomas (regulares) como base e queremos dizer algo sobre uma linguagem derivada dele. Seguindo a primeira abordagem - construa um modelo adequado para - podemos assumir o modelo equivalente a que desejamos; permanecerá abstrato, é claro, já que é desconhecido. Na segunda abordagem, podemos usar diretamente e aplicar propriedades de fechamento para obter uma descrição para .L L L L L L LLLLLLL

Tocou.
fonte
4
Também pode ser interessante notar que provar que um idioma é finito é suficiente para mostrar que é regular. Isso pode ser útil, principalmente em provas não construtivas por casos.
precisa saber é o seguinte
2
As expressões regulares de regexp encontradas nas linguagens de programação podem fazer muito mais do que as linguagens regulares. Você teria que restringir a construções "clássicas".
David Lewis
4
@ DavidLewis: Neste site, você pode supor que por "expressão regular" se entende a noção clássica.
Raphael
@ DavidLewis Concordo, deve-se evitar "regexp" no contexto da teoria para evitar confusão.
Raphael
Observe que, para qualquer um dos quatro primeiros marcadores, você precisará de uma prova mostrando que sua representação está realmente correta.
Raphael
10

Métodos elementares

  1. Autômatos finitos (possivelmente não determinísticos, com transições vazias).
  2. Expressões regulares.
  3. Equações lineares direita (ou esquerda, mas não ambas), como onde e são regulares.K LX=KX+LKL
  4. Gramática regular (tipo 3).
  5. Operações que preservam linguagens regulares (operações booleanas, produto, estrela, shuffle, morfismos, inversas de morfismos, reversão etc.)
  6. Reconhecido por um monóide finito.

Métodos lógicos (geralmente usados ​​na verificação formal)

  1. Lógica monádica de segunda ordem (teorema de Büchi).
  2. Lógica temporal linear (teorema de Kamp).
  3. Teorema da árvore de Rabin (lógica monádica de segunda ordem com dois sucessores). Muito poderoso.

Métodos avançados

  1. Lemas sofisticados de bombeamento. Veja, por exemplo,
    [1] J. Jaffe, um lema de bombeamento necessário e suficiente para idiomas regulares, Sigact News - SIGACT 10 (1978) 48-49.
    [2] A. Ehrenfeucht, R. Parikh e G. Rozenberg, Lemmas de bombeamento para conjuntos regulares, SIAM J. Comput. 10 (1981), 536-541.
    [3] S. Varricchio, Uma condição de bombeamento para conjuntos regulares, SIAM J. Comput. 26 (1997) 764-771.

  2. Bem quase ordens. Ver
    [4] W. Bucher, A. Ehrenfeucht, D. Haussler, Sobre reguladores totais gerados por relações de derivação, Theor. Comput. Sci. 40 (1985) 131-148.
    [5] M. Kunz, soluções regulares de desigualdades de linguagem e quase-ordens de poço .

  3. Suporte à série .N

  4. Métodos algébricos baseados em transduções (consulte também Operações preservando idiomas regulares ).

J.-E. PIN
fonte
4

A resposta de Ran G. fornece uma lista bastante extensa dos modelos equivalentes que podem ser usados ​​para especificar idiomas regulares (e a lista continua, autômatos bidirecionais, lógica MSO, mas isso é coberto pelo link em 'modelos mais equivalentes '). E, como Raphael enfatiza, precisamos de um argumento para convencer o público de que a representação escolhida é realmente correta.

Reconsiderando a pergunta, ele adiciona 'Por exemplo '. Isso significa que precisamos fornecer uma construção válida que, considerando qualquer um dos modelos acima, assumimos que especifique a linguagem , transforme esse modelo em um para . Esse geralmente será o mesmo tipo de modelo, mas não precisa ser: podemos, por exemplo, começar com uma FSA determinística para e terminar com uma não determinística para .LLLL

Isso inclui a possibilidade de usar operações de fechamento: na operação fornecida explicitamente no exemplo, temos .L=(ΣL)Σ

Portanto, o que quero dizer é que a resposta é ótima, mas devemos adicionar a "construção de para ", quando não estiver construindo um idioma específico a partir do zero.LL

Hendrik Jan
fonte
1
Não tenho muita certeza do que você está falando. Se eu tiver algum modelo para , posso convertê-lo em qualquer um dos outros equivalentes. L
Raphael
@ Rafael Desculpe, eu fiz o meu ponto. As respostas anteriores parecem explicar que podemos construir uma descrição da linguagem (como autômato, operações, etc.). Concordo. No entanto, a pergunta parece ser sobre propriedades de fechamento, veja o exemplo dado. Falto nesse ponto nas outras respostas: para provar uma propriedade de fechamento, você assume que tem uma descrição e constrói uma nova.
Hendrik Jan
1
Ah, esse ! Agora entendi, meu mal. Eu concordo, esse aspecto está faltando na resposta de Ran. L
Raphael
1
Não sei por que está faltando (ou o que exatamente está faltando). Digamos que você tenha um regular'e você quer provar é regular, bem, você pode começar com 's DFA e usá-lo para construir um DFA para . Mas isso é coberto por "construir um DFA para ". Não há restrição para usar autômato para essa tarefa (e, naturalmente, se for definido via você será forçado a usar o autômato ). . O mesmo vale para regexp, fechamento, gramáticas, etc.LLLLLLLLL
Ran G.
1
Ah ok. Na verdade, prefiro editar a pergunta e remover a parte "por exemplo", tornando a pergunta mais geral e uma referência para futuras perguntas semelhantes. (:
Ran G.
4

Ocasionalmente, você encontrará um idioma especificado como "todas as cadeias de caracteres onde cada substring do elemento de satisfaz ", onde é alguma constante fixa. Nesse caso, o idioma será regular. A idéia aqui é definir um autômato finito em que alguns dos estados "lembram" os símbolos de entrada vistos mais recentemente , como na resposta a esta pergunta .sks<some property>kk

Rick Decker
fonte
4

Outro método, não coberto pelas respostas acima, é a transformação finita de autômatos . Como um exemplo simples, vamos mostrar que os idiomas regulares estão fechados na operação de reprodução aleatória , definida da seguinte forma: Você pode mostrar o fechamento em ordem aleatória usando as propriedades de fechamento, mas também pode mostrá-lo diretamente usando os DFAs. Suponha que seja um DFA que aceite (para ). Construímos um novo DFA seguinte maneira:

L1SL2={x1y1xnynΣ:x1xnL1,y1ynL2}
Ai=Σ,Qi,Fi,δi,q0iLii=1,2Σ,Q,F,δ,q0
  • O conjunto de estados é , onde o terceiro componente se lembra se o próximo símbolo é um (quando 1) ou (quando 2).Q1×Q2×{1,2}xiyi
  • O estado inicial é .q0=q01,q02,1
  • Os estados de aceitação são .F=F1×F2×{1}
  • A função de transição é definida por e .δ(q1,q2,1,σ)=δ1(q1,σ),q2,2δ(q1,q2,2,σ)=q1,δ2(q2,σ),1

Uma versão mais sofisticada desse método envolve adivinhação . Como exemplo, vamos mostrar que os idiomas regulares são fechados sob reversão , ou seja, (Aqui .) Essa é uma das operações de fechamento padrão, e o fechamento com reversão ocorre facilmente com a manipulação de expressões regulares (que pode ser considerada a contrapartida da transformação de autômatos finitos em expressões regulares) - apenas inverta a expressão regular. Mas você também pode provar o fechamento usando NFAs. Suponha que seja aceito por um DFA . Construímos um NFA

LR={wR:wΣ}.
(w1wn)R=wnw1LΣ,Q,F,δ,q0Σ,Q,F,δ,q0 , em que
  • O conjunto de estados é .Q=Q{q0}
  • O estado inicial é .q0
  • O estado de aceitação exclusivo é .q0
  • A função de transição é definida da seguinte maneira: e para qualquer estado e , .δ(q0,ϵ)=FqQσΣδ(q,σ)={q:δ(q,σ)=q}

(Podemos nos livrar de se permitirmos vários estados iniciais.) O componente de adivinhação aqui é o estado final da palavra após a reversão.q0


Adivinhar muitas vezes envolve também verificar. Um exemplo simples é o fechamento em rotação : Suponha que seja aceito pelo DFA . Construímos um NFA , que opera da seguinte maneira. O NFA adivinha primeiro . Em seguida, verifica se e que , movendo-se de para não determinística. Isso pode ser formalizado da seguinte maneira:

R(L)={yxΣ:xyL}.
LΣ,Q,F,δ,q0Σ,Q,F,δ,q0q=δ(q0,x)δ(q,y)Fδ(q0,x)=qyx
  • Os estados são . Além do estado inicial , os estados são , onde é o estado que adivinhámos, é o estado atual especifica se estamos em a parte da entrada (quando 1) ou na parte da entrada (quando 2).Q={q0}Q×Q×{1,2}q0q,qcurr,sqqcurrsyx
  • Os estados finais são : aceitamos quando .F={q,q,2:qQ}δ(q0,x)=q
  • As transições implementam a adivinhação .δ(q0,ϵ)={q,q,1:qQ}q
  • As transições (para cada e ) simulam o DFA original.δ(q,qcurr,s,σ)=q,δ(qcurr,σ),sq,qcurrQs{1,2}
  • As transições , para cada e , implementam o movimento da parte para a parte. Isso só é permitido se atingirmos um estado final na parte .δ(q,qf,1,ϵ)=q,q0,2qQqfFyxy

Outra variante da técnica incorpora contadores limitados. Como exemplo, vamos considerar o fechamento da distância de edição de alteração : Dado um DFA para , e construa um NFA para do seguinte modo:

Ek(L)={xΣ: there exists yL whose edit distance from x is at most k}.
Σ,Q,F,δ,q0LΣ,Q,F,δ,q0Ek(L)
  • O conjunto de estados é , em que o segundo item conta o número de alterações feitas até o momento.Q=Q×{0,,k}
  • O estado inicial é .q0=q0,0
  • Os estados de aceitação são .F=F×{0,,k}
  • Para cada temos transições .q,σ,iδ(q,σ),iδ(q,i,σ)
  • As inserções são manipuladas pelas transições para todos os modo que .q,i+1δ(q,i,σ)q,σ,ii<k
  • As exclusões são manipuladas por transições para todos os modo que .δ(q,σ),i+1δ(q,i,ϵ)q,σ,ii<k
  • As substituições são identificadores semelhantes pelas transições para todos os tal que .δ(q,σ),i+1δ(q,i,τ)q,σ,τ,ii<k
Yuval Filmus
fonte
3

Um idioma é regular se você puder escrever um scanner que decida sobre seqüências arbitrárias, se pertencem ou não ao idioma, usando não mais do que uma quantidade fixa de memória - ou seja, o reconhecimento pode ser feito no espaço O (1) .

reinierpost
fonte
O (1) espaço, você quer dizer? De qualquer forma, isso é coberto pelo fato de o DFA ser suficiente; pode valer a pena observar explicitamente essa equivalência em termos de programação.
Raphael
Sim, é apenas uma perspectiva diferente.
Reinierpost
3

A transformação de expressão regular é uma maneira de provar o fechamento em determinadas operações. Os dois exemplos mais simples são fechamento sob reversão e fechamento sob homomorfismo .

Dada uma expressão regular representando uma linguagem , podemos construir uma expressão regular para , a linguagem do verso de todas as palavras em , recursivamente:rLLRL

  • ϵR=ϵ , , .σR=σR=
  • (r1+r2)R=(r1R+r2R) , , .(r)R=(rR)(r1r2)R=r2Rr1R

Toda a ação acontece no final regra . Como exemplo, você pode verificar se . Estabelece indução estruturais que a linguagem da é, de fato . ( 0 1 ) R = 1 0 r R L R(r1r2)R=r2Rr1R(01)R=10rRLR

Outro exemplo simples é o fechamento sob homomorfismo. Dado um homomorfismo e uma expressão regular para uma linguagem , podemos obter uma expressão regular para substituindo todas as instâncias de em por . r L h ( L ) σ r h ( σ )h:ΣΔrLh(L)σrh(σ)

Yuval Filmus
fonte
0

Outra maneira é criar o idioma usando operações nas quais você sabe que eles estão fechados. Esta é uma extensão para exibir uma expressão regular, pois você tem muito mais operações disponíveis (inverter a corda, complemento, interseção, cortar um pedaço, apenas manter uma parte, homomorfismos e homomorfismos inversos, ...)

vonbrand
fonte
2
Isso já foi mencionado na resposta de Ran.
Raphael