O idioma das palavras que contém o número igual de 001 e 100 é regular?

14

Fiquei me perguntando quando os idiomas que continham o mesmo número de instâncias de duas substrings seriam regulares. Eu sei que o idioma que contém o número igual de 1s e 0s não é regular, mas é um idioma como , onde = número de instâncias da substring "001" é igual ao número de instâncias da substring " 100 " regular? Observe que a string "00100" seria aceita.eueu{W}

Minha intuição me diz que não é, mas sou incapaz de provar isso; Não posso transformá-lo em uma forma que possa ser bombeada através do lema de bombeamento, então como posso provar isso? Por outro lado, tentei criar um DFA ou um NFA ou uma expressão regular e falhei nessas frentes também, então como devo proceder? Eu gostaria de entender isso em geral, não apenas para a linguagem proposta.

Ben Elgar
fonte
2
Por que você não pode responder sua própria solução?
Yuval Filmus
1
@YuvalFilmus Há um atraso para os usuários de baixa reputação responderem à sua própria pergunta (8 horas se o representante for <100).
Gilles 'SO- stop be evil'
1
Provavelmente deve haver um loop adicional no ? 0 0q5
precisa
1
Um exemplo similar desse fenômeno, mas para os substrings "01" e "10" foi discutido em nosso site irmã Provando uma linguagem é regular ou irregular . A resposta tem uma observação semelhante à que foi feita em seu comentário: "Ou seja, uma transição 01 não pode ser seguida por outra transição sem uma transição intermediária ". 0110
precisa

Respostas:

3

Uma resposta extraída da pergunta.

Como apontado por Hendrik Jan, deve haver um auto-loop 0 adicional no q5.

autômato

Juho
fonte
esta é uma construção, não uma prova
vzn
nas aulas de CS para problemas simples, às vezes, apenas DFAs são fornecidos, mas isso não prova que ele aceita exatamente o idioma. você tem que [de alguma forma] mostrar para cada string de entrada que ela funciona corretamente. "como funciona?"
vzn
2
Eu acho que você pode mesclar e . Isso está certo? q5q2
J.-E.
3

É uma pergunta complicada. Tente construir uma sequência que contenha dois 001 e não contenha 100 e veja por que você não pode fazê-lo. Se X = "número de 001" e Y = "número de 100", X = Y ou X = Y ± 1.

Depois que você realiza o truque, torna-se altamente improvável que o idioma seja irregular e a construção de um DFA é bastante simples. Existem apenas 8 estados com suas transições se o próximo símbolo for 0/1:

State S0: Input is empty. -> S1/C0

State S1: Input is 0. -> C2/C0

State A: Y = X + 1, input ends in 00. -> A/C0

State B0: X = Y + 1, input ends in 1. -> B1/B0

State B1: X = Y + 1, input ends in 10. -> C2/B0

State C0: X = Y, input ends in 1. -> C1/C0

State C1: X = Y, input ends in 10. -> A/C0

State C2: X = Y, input ends in 00. -> C2/B0

O estado inicial é S0, e S0, S1, C0, C1, C2 são estados de aceitação.

gnasher729
fonte