Provar que o idioma é regular ou não regular

Deixei $L$ ser uma linguagem regular. Prove que:

$L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$

$L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$

$L_{-+-}=\left\{w:\exists_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\}$

são regulares e:

$L_{+-+}=\left\{ uv:\exists_w |u|=|w|=|v| \wedge uwv\in L \right\}$

não é regular.

Parece muito difícil para mim. Suponho que 1-3 sejam semelhantes (mas posso estar errado), mas não sei como abordar. A idéia geral é geralmente modificar a máquina de estados finitos para $L$ para aceitar outro idioma. Mas essas construções geralmente são muito sofisticadas e eu ainda não consigo fazer isso sozinha.

regular-languages xan
fonte

possível duplicata de Como provar que um idioma não é regular?

Bartosz Przybylski

Não tenho certeza de que suas afirmações estejam corretas, porque pelo teorema de Myhill-Nerode parece que as três primeiras línguas têm infinitas classes de equivalência! para o primeiro: tome

w_{i}

$w_i$ seja o i-ésimo em

L_{+ - -}

$L_{+--}$ e

w_{i + 1}

$w_{i+1}$ seja a (i + 1) -ésima palavra, para cada i que puder escolher

u_{i}

$u_i$ para mostrar que existe uma palavra que separa as classes de

w_{i}

$w_i$ e

w_{i + 1}

$w_{i+1}$

Fayez Abdlrazaq Deab

@Fayez E se, por exemplo,

L = Σ^{*}

$L=\Sigma^*$ ? Então

L_{+ - -} = Σ^{*}

$L_{+--} = \Sigma^*$ possui apenas uma classe de equivalência. Examine sua prova e veja o que está errado.

Yuval Filmus

A @Bartek e qualquer outra pessoa que está votando para fechar: metade da questão é realmente provar que certas operações em idiomas conservam a propriedade de serem regulares.

Yuval Filmus

Respostas:

Aqui está uma prova de que o idioma $L_0 = \{ w : \exists_u |u|=|w| \land uw \in L \}$ é regular. Pode ser modificado para mostrar que os três primeiros da sua lista são regulares. (Observe que eu mudei $wu$ para $uw$ .) Dado um DFA para $L$ , criamos um NFA para $L_0$ . A primeira coisa que a NFA faz é adivinhar (faça uma $\epsilon$ mover) um estado $q$ , cuja semântica pretendida é o estado em que o DFA para $L$ acaba depois de ler $u$ . Em seguida, ele executa simultaneamente duas cópias do DFA para $L$ , um começando no estado inicial e outro começando em $q$ . Ao ler um símbolo $a$ , ele se move de acordo com um símbolo arbitrário no primeiro e se move de acordo com $a$ no segundo. Um estado está aceitando se a primeira cópia estiver no estado $q$ e o segundo está em um estado de aceitação.

Para a final, considere o idioma $L= a^+ b^+ c^+$ e cruzar $L_{+-+}$ com $a^+ c^+$ .

Yuval Filmus
fonte

Eu não vejo isso.

L = a^{+} b^{+} c^{+} \Rightarrow L_{+ - +} \cap a^{+} c^{+} = {a^{n} c^{m} : n + m \equiv_{2} 0}

$L=a^+b^+c^+ \Rightarrow L_{+-+} \cap a^+c^+=\left\{ a^n c^m: n+m\equiv_2 0 \right\}$ , que é claramente um idioma comum. Mas suponho que estou errado :) Você pode me indicar a direção certa?

xan

Consegui modificar sua construção de

L_{0}

$L_0$ e até remover

ε

$\varepsilon$ move para que fique mais elegante (na minha opinião). Portanto, os três primeiros problemas foram resolvidos e obrigado por isso! :) Mas a única coisa que peço é esclarecer a última e minhas preocupações no comentário acima. Eu ficaria muito agradecido.

xan

Quando eu computo

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+} \cap a^+ c^+$ Eu recebo outra coisa. Observe que toda palavra em

L

$L$ deve conter um

b

$b$ .

Yuval Filmus

Desculpe, mas não sei calcular

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+}\cap a^+c^+$ . Suponho que o resultado seja

{a^{n} c^{n} : n \in N}

$\left\{ a^n c^n: n\in\mathbb{N}\right\}$ o que nos dá o que queremos, mas simplesmente não sei como justificar isso.

xan

Ok, eu posso ver agora :-)

xan