La langue des mots contenant un nombre égal de 001 et 100 est-elle régulière?

Je me demandais quand les langues contenant le même nombre d'instances de deux sous-chaînes seraient régulières. Je sais que le langage contenant un nombre égal de 1 et de 0 n'est pas régulier, mais est un langage tel que , où = nombre moyen d'instances de la sous-chaîne "001" est égal au nombre d'instances de la sous-chaîne " 100 " régulier? Notez que la chaîne "00100" serait acceptée. $L$ $L$ $\{ w \mid$ $\}$

Mon intuition me dit que non, mais je ne peux pas le prouver; Je ne peux pas le transformer en une forme qui pourrait être pompée via le lemme de pompage, alors comment puis-je le prouver? D'un autre côté, j'ai essayé de créer un DFA ou un NFA ou une expression régulière et j'ai échoué sur ces fronts également, alors comment dois-je procéder? Je voudrais comprendre cela en général, pas seulement pour la langue proposée.

formal-languages regular-languages pumping-lemma Ben Elgar
la source

Avez-vous vu Comment prouver qu'une langue n'est pas régulière ?

Juho

Pourquoi ne pouvez-vous pas répondre à votre propre solution?

Yuval Filmus

@YuvalFilmus Il y a un délai pour que les utilisateurs de mauvaise réputation répondent à leur propre question (8 heures si rep <100).

Gilles 'SO- arrête d'être méchant'

Il devrait probablement y avoir une boucle

supplémentaire à

0

$0$

q 5

$q5$

Hendrik Jan

Un exemple similaire de ce phénomène, mais pour les sous-chaînes "01" et "10" a été discuté sur notre site frère Prouver une langue est régulière ou irrégulière . La réponse a une remarque similaire à celle formulée dans son commentaire: "C'est-à-dire qu'une transition 01 ne peut pas être suivie d'une autre transition

sans une transition

intermédiaire .".

01

$01$

10

$10$

Hendrik Jan

Réponses:

Une réponse extraite de la question.

Comme l'a souligné Hendrik Jan, il devrait y avoir une boucle automatique supplémentaire de 0 à q5.

automate

Juho
la source

c'est une construction, pas une preuve

vzn

dans les classes CS pour des problèmes simples, parfois, seuls les DFA sont donnés, mais cela ne prouve pas qu'il accepte exactement le langage. vous devez [en quelque sorte] montrer que chaque chaîne d'entrée fonctionne correctement. "Comment ça marche?"

vzn

q_{5}

$q_5$

q_{2}

$q_2$

C'est une question piège. Essayez de construire une chaîne qui contient deux 001 et ne contient pas de 100, et voyez pourquoi vous ne pouvez pas le faire. Si X = "nombre de 001" et Y = "nombre de 100", alors X = Y ou X = Y ± 1.

Une fois que vous avez réalisé l'astuce, il devient hautement improbable que le langage soit irrégulier, puis la construction d'un DFA est assez simple. Il n'y a que 8 états avec leurs transitions si le symbole suivant est 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

L'état initial est S0, et S0, S1, C0, C1, C2 sont des états accepteurs.

gnasher729
la source