É decidível se um idioma descrito por número de ocorrências é regular?

14

Sabe-se que o idioma das palavras que contêm número igual de 0 e 1 não é regular, enquanto o idioma das palavras que contêm número igual de 001 e 100 é regular ( veja aqui ).

Dadas duas palavras w1,w2 , é decidível se o idioma das palavras que contêm o mesmo número de e é regular?w1w2

sdcvvc
fonte
Você pode dar outros exemplos de linguagens regulares assim definidas, além de e ou e ? Que tal um exemplo em um alfabeto de 3 símbolos? 01 i 0 i 1 10 i1i001i0i110i
21713
Se w1 é um subword estrita de w2 , há uma grande chance da linguagem é vazia, portanto, regular. Não conheço outros exemplos.
Sdcvvc
Suspeito que os exemplos acima sejam os únicos, o que tornaria o problema decidível. Se você especificar apenas duas substrings, acho que é CF ... dependendo do que você pode especificar em relação às ocorrências. Você não torna suficientemente preciso o que quer dizer com "descrito pelo número de ocorrências".
21713
O corpo da pergunta é IMO preciso o suficiente.
Sdcvvc
1
as soluções até agora para casos especiais parecem depender da ideia de que ocorrências de substrings de garantem apenas ocorrências únicas de w 2 intervenientes . então, de alguma forma, supondo que as respostas atuais estejam corretas [ainda não está claro para mim], parece que existe alguma relação entre w 1 , w 2 que garante, no meio da varredura, a sequência de caracteres que pode ser encontrada nos estados "iguais" ou "desiguais" ", mas apenas desativado por um número finito máximo para o caso" desigual ". w1w2w1w2
vzn

Respostas:

3

Dadas duas palavras , w 2 , é decidível se a linguagem L de palavras contendo número igual de w 1 e w 2 é regular?w1w2Lw1w2

Primeiro, algumas definições:
elas poderiam ser mais concisas e as notações poderiam ser melhoradas se fossem usadas em provas. Este é apenas um primeiro rascunho.

Dadas duas palavras e w 2 , dizemos que: w1w2

  • sempre ocorrecom w 2 , observado w 1w 2 , se w1 w2w1w2

    1. para qualquer string tal que s = x w 2 y com x ,ss=xw2y e | x | 0 , | x | 1 | , | y | 0 , | y | 1 | 1 existe outra decomposição s = x ' w 1 y ' . Nota: A condição em que x e yx,y ≥∣w1+w2|x|0,|x|1|,|y|0,|y|1|1s=xw1y
      xycada um contém pelo menos um 0 e um 1 é exigido por um caso patológico (encontrado por @sdcvvc): , w 2 = v 1 i + j e y 1 e suas variantes simétricas.w1=1i0w2=v1i+jy1
    2. existe uma string com x ,s=xw2y modo que exista no máximo uma decomposição s = x w 1 y x,y ≥∣w1+w2s=xw1y
  • sempre co-ocorrecom w 2 , observado w 1w1 w2 , se cada um ocorrer sempre com o outro,w1w2

  • e w 2 ocorrem independentemente, observado w 1w1w2 , se nem sempre um ocorre com o outro,w1w2

  • sempre ocorre m vezes ou maisdo que w 2 , observou w 1 m w 2 , sse para qualquer cadeia s tais que s = x w 2w1 mw2w1mw2s com | X | , | y | | w 1+ w 2 existem m outras decomposições s = x i w 1 y is=xw2yx, y| ≥∣w1+w2ms=xiw1yipara tal que i j implica x ix j .i[1,m]ijxixj

Essas definições são construídas para que possamos ignorar o que acontece nas extremidades da cadeia de caracteres onde e w 2 devem ocorrer. Os efeitos de limite no final da string precisam ser analisados ​​separadamente, mas representam um número finito de casos (na verdade, acho que esqueci um ou dois sub-casos de limite na minha primeira análise abaixo, mas isso realmente não importa). As definições são compatíveis com a sobreposição de ocorrências.w1w2

Há quatro casos principais a serem considerados (ignorando a simetria entre e w 2 ):w1w2

  1. w1w2
    Ambas as palavras se juntam necessariamente, exceto, possivelmente, no final da string. Trata-se apenas de pares dos formatos e 01 i , ou 0 i 1 e 10 i . Isso é facilmente reconhecido por um autômato finito que apenas verifica a ocorrência de ocorrências isoladas nas duas extremidades da cadeia, para garantir que exista uma ocorrência isolada nas duas extremidades ou nas extremidades. Há também o caso degenerado quando w 1 = w 2 : então a linguagem L é obviamente regular.1i001i0i110iw1=w2

  2. , mas não w 2w 1 Uma das 2 palavras não pode ocorrer sem a outra, mas o inverso não é verdadeiro (exceto possivelmente no final da cadeia). Isso acontece quando:w1w2w2w1

    • é uma substring de w 2 : então um autômato finito pode apenas verificar se w 1 não ocorre fora de uma instância de w 2 .w1w2w1w2

    • e w 2 = v 1 j para alguma palavra v { 0 , 1 } , v 01 i : então, um autômato finito verifica como no caso anterior que w 1 não ocorre separado de w 2 . No entanto, o autômato permite contar uma instância extra de w 1 que permitirá a aceitação se w 2w1=1i0w2=v1jv{0,1}v01iw1w2w1w2é um sufixo da sequência. Existem outros três casos simétricos (simetria 1-0 e simetria esquerda-direita).

  3. Uma das 2 palavras ocorre duas vezes na outra. Isso pode ser reconhecido por uma automação finita que verifica se a palavra menor nunca ocorre na string. Também é uma variante um pouco mais complexa que combina as duas variações do caso 2. Nesse caso, o autômato verifica se a cadeia menor 1 i 0 nunca ocorre, exceto possivelmente como parte de v na maior v 1 j como sufixo da string (e 3 outros casos por simetria).w12w2
    1i0vv1j

  4. As 2 palavras podem ocorrer independentemente uma da outra. Construímos uma sequencial-máquina generalizada (gsm) G que a saída de um quando reconhece uma ocorrência de w 1 e b durante o reconhecimento de uma ocorrência de w 2 , e esquece-se tudo o resto. O idioma L é regular apenas se o idioma G ( L ) for regular. Mas G ( L ) = { w { a , b } w aw1w2
    Gaw1bw2LG(L) que é claramente livre de contexto e não regular. Portanto, L não é regular. Na verdade, temos L = G - 1 ( G ( L ) ) . Como linguagens regulares e linguagens livres de contexto são fechadas sob o mapeamento gsm e o mapeamento gsm inverso, sabemos também que L é livre de contexto.G(L)={w{a,b} wa=∣wb}L
    L=G1(G(L))L

Uma maneira de organizar uma prova formal pode ser a seguinte. Primeiro, crie um PDA que reconheça o idioma. Na verdade, isso pode ser feito com uma máquina de 1 balcão, mas é mais fácil ter dois símbolos de pilha para evitar duplicar o controle finito. Então, para os casos em que deveria ser um FA, mostre que o contador pode ser delimitado por uma constante que depende apenas das duas palavras. Para os outros casos, mostre que o contador pode atingir qualquer valor arbitrário. Obviamente, o PDA deve ser organizado de modo que as provas sejam fáceis de transportar.

Representar o FA como um PDA com 2 símbolos de pilha é provavelmente a representação mais simples para ele. No caso não regular, a parte de controle finito do PDA é a mesma do GSM no esboço de prova acima. Em vez de emitir 'e ' b como o GSM, o PDA conta a diferença em número com a pilha.ab

babou
fonte
Eu tive uma pergunta sobre ausência de contexto no caso de três palavras. Excluí-o quando percebi que poderia ser analisado da mesma forma. Eu primeiro pensei que provar que não era CFness seria um exercício original, mas o GSM o estraga.
21713
2
Não está claro o que você quer dizer com "ocorrer independentemente um do outro", "reunir-se necessariamente" etc. etc. Em vez disso, escreva definições formais e prove que elas cobrem todos os casos.
precisa
1
Não tenho certeza do que você está perguntando e que nível de formalização você precisa, para qual propósito. Percebi que a análise manual de possíveis relações das duas palavras não é garantida como correta, e isso não importa. O que importa é se uma ocorrência de uma palavra pode existir sem criar ao mesmo tempo uma ocorrência (ou várias) da outra palavra. Os detalhes não importam, pois sempre serão localizados e, portanto, gerenciáveis ​​finitamente. As duas extremidades também não importam, pois também estão localizadas. Mesmo se sobrepõe de ocorrências não importa, uma vez que só pode ser finita muitos em 1 lugar
babou
1
Perguntei sobre definições precisas dos termos mencionados no comentário. Obrigado por escrevê-los. Eu deveria adivinhar eles anteriormente? De qualquer forma, você parece afirmar que . Isso não satisfaz a condição 1. da definição de " w 1 sempre ocorre com w 2 ", pois não há ocorrência de 1 0 i em s = 0 M 0 i 1 1 M0i110iw1w210is=0M0i11M .
Sdcvvc
Desculpe, não tive a intenção de fazer você adivinhar. Levei apenas tempo para entender o que exatamente você queria. Minha falha apenas. Em relação ao seu exemplo de contador, você está correto. Mas, para mim, isso significa apenas que tenho que ter um pouco mais de cuidado com os telômeros, na definição das relações. Eu os defini muito rapidamente, mas ou 1 M não transmitem muita informação neste contexto. Este é realmente um exemplo patológico de fronteira dentro de um caso patológico, que na verdade não pode ocorrer quando mais de 2 símbolos são usados. Eu simplesmente não acredito que isso mude alguma coisa. 0M1M
babou