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

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. $L$ $L$ $\{ w \mid$ $\}$

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.

formal-languages regular-languages pumping-lemma Ben Elgar
fonte

Você viu Como provar que um idioma não é regular ?

Juho

Por que você não pode responder sua própria solução?

Yuval Filmus

@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'

Provavelmente deve haver um loop adicional no ?

0

$0$

q 5

$q5$

precisa

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 ".

01

$01$

10

$10$

precisa

Respostas:

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

Eu acho que você pode mesclar e . Isso está certo?

q_{5}

$q_5$

q_{2}

$q_2$

J.-E.

É 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