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?LLL′L′
Posso desenhar um autômato finito não determinístico para provar isso?
há um erro de digitação na definição do seu , edite para corrigir. L′L′L′L′
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.
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".
@ DavidLewis: Neste site, você pode supor que por "expressão regular" se entende a noção clássica.
@ DavidLewis Concordo, deve-se evitar "regexp" no contexto da teoria para evitar confusão.
Observe que, para qualquer um dos quatro primeiros marcadores, você precisará de uma prova mostrando que sua representação está realmente correta.
Métodos elementares
Autômatos finitos (possivelmente não determinísticos, com transições vazias).
Equações lineares direita (ou esquerda, mas não ambas), como onde e são regulares.K LX=KX+LX=KX+LKKLL
Gramática regular (tipo 3).
Operações que preservam linguagens regulares (operações booleanas, produto, estrela, shuffle, morfismos, inversas de morfismos, reversão etc.)
Reconhecido por um monóide finito.
Métodos lógicos (geralmente usados ​​na verificação formal)
Lógica monádica de segunda ordem (teorema de Büchi).
Lógica temporal linear (teorema de Kamp).
Teorema da árvore de Rabin (lógica monádica de segunda ordem com dois sucessores). Muito poderoso.
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.
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 .
Suporte à série .NN
Métodos algébricos baseados em transduções (consulte também Operações preservando idiomas regulares ).
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 .……LLL′L′
Isso inclui a possibilidade de usar operações de fechamento: na operação fornecida explicitamente no exemplo, temos .L′=(Σ∗∖L)⋅Σ∗L′=(Σ∗∖L)⋅Σ∗
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′L′
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.L′L′LLLLL′L′L′L′
O estado de aceitação exclusivo é .q0q0
A função de transição é definida da seguinte maneira: e para qualquer estado e , .δ′(q′0,ϵ)=Fδ′(q0′,ϵ)=Fq∈Qq∈Qσ∈Σσ∈Σδ(q′,σ)={q:δ(q,σ)=q′}δ(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.q′0q0′⟨q,qcurr,s⟩⟨q,qcurr,s⟩qqqcurrqcurrssyyxx
Os estados finais são : aceitamos quando .F′={⟨q,q,2⟩:q∈Q}F′={⟨q,q,2⟩:q∈Q}q,qcurr∈Qq,qcurr∈Qs∈{1,2}s∈{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,2⟩δ′(⟨q,qf,1⟩,ϵ)=⟨q,q0,2⟩
O estado inicial é .q′0=⟨q0,0⟩q0′=⟨q0,0⟩
Para cada temos transições .q,σ,iq,σ,i⟨δ(q,σ),i⟩∈δ′(⟨q,i⟩,σ)⟨δ(q,σ),i⟩∈δ′(⟨q,i⟩,σ)q,σ,iq,σ,ii<ki<k
As exclusões são manipuladas por transições para todos os modo que .⟨δ(q,σ),i+1⟩∈δ′(⟨q,i⟩,ϵ)⟨δ(q,σ),i+1⟩∈δ′(⟨q,i⟩,ϵ)q,σ,τ,iq,σ,τ,ii<ki<k
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) .
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.
Sim, é apenas uma perspectiva diferente.
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:rrLLLRLRLL
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=rR2rR1(r1r2)R=r2Rr1R(0∗1∗)R=1∗0∗(0∗1∗)R=1∗0∗rRrRLRLR
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:Σ→Δ∗h:Σ→Δ∗rrLLh(L)h(L)σσrrh(σ)h(σ)
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, ...)