¿Es regular el lenguaje de las palabras que contienen igual número de 001 y 100?

Me preguntaba cuándo los idiomas que contenían el mismo número de instancias de dos subcadenas serían regulares. Sé que el idioma que contiene el mismo número de 1s y 0s no es regular, pero es un lenguaje como , donde = número de instancias de la subcadena "001" es igual al número de instancias de la subcadena "100" regular? Tenga en cuenta que la cadena "00100" sería aceptada. $L$ $L$ $\{ w \mid$ $\}$

Mi intuición me dice que no, pero no puedo demostrarlo; No puedo transformarlo en una forma que pueda bombearse a través del lema de bombeo, entonces, ¿cómo puedo probar eso? Por otro lado, he intentado construir un DFA o un NFA o una expresión regular y también he fallado en esos frentes, entonces, ¿cómo debo proceder? Me gustaría entender esto en general, no solo por el lenguaje propuesto.

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

¿Viste Cómo probar que un idioma no es regular ?

Juho

¿Por qué no puedes responder tu propia solución?

Yuval Filmus

@YuvalFilmus Hay un retraso para que los usuarios de baja reputación respondan sus propias preguntas (8 horas si rep <100).

Gilles 'SO- deja de ser malvado'

¿Probablemente debería haber un bucle

adicional en

0

$0$

q 5

$q5$

Hendrik

Un ejemplo similar de este fenómeno, pero para las subcadenas "01" y "10" se discutió en nuestro sitio hermano. Probar un idioma es regular o irregular . La respuesta tiene una observación similar a la de Wece en su comentario: "Es decir, una transición 01 no puede ser seguida por otra transición

sin una transición

intermedia ".

01

$01$

10

$10$

Hendrik

Respuestas:

Una respuesta extraída de la pregunta.

Como señaló Hendrik Jan, debería haber un 0 auto-loop adicional en q5.

autómata

Juho
fuente

esta es una construcción, no una prueba

vzn

en clases de CS para problemas simples, a veces solo se dan DFA, pero no prueba que acepte exactamente el lenguaje. tienes que mostrar [de alguna manera] para cada cadena de entrada que funciona correctamente. "¿como funciona?"

vzn

q_{5}

$q_5$

q_{2}

$q_2$

Es una pregunta capciosa. Intente construir una cadena que contenga dos 001 y no contenga un 100, y vea por qué no puede hacerlo. Si X = "número de 001" e Y = "número de 100", entonces X = Y o X = Y ± 1.

Una vez que se da cuenta del truco, es muy poco probable que el lenguaje sea irregular, y luego construir un DFA es bastante simple. Solo hay 8 estados con sus transiciones si el siguiente símbolo es 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

El estado inicial es S0, y S0, S1, C0, C1, C2 son estados de aceptación.

gnasher729
fuente