$ \ mathcal {g}={v_2 v_4 \ ldots v_ {k}: v_1 v_2 v_3 v_4 \ ldots v_ {k-1} v_ {k} \ \ mathcal {l}, \ text} mesmo}\} $ é linguagem livre de contexto

Question

Deixe $ \ mathcal {l} $ Seja de contexto Linguagem livre sobre o alfabeto $ \ sigma $ . Definir $ \ mathcal {g} $ como $$ \ mathcal {g}={v_2 v_4 \ ldots v_ {k}: v_1 v_2 v_3 v_4 \ ldots v_ {k-1} v_ {k} \ in \ mathcal {k-1} L}, \ text {$ k $ par}} $$

Eu já vi um pergunta semelhante (perguntou há 5 anos), mas não tenho certeza de como isso pode funcionar.

Proposição

$ \ mathcal {L} $ é CFL para que tenha o próprio automata push-down. Então deixe cópia estados de $ \ mathcal {l} $ e se tiver um estado chamado $ s $ e ele chega ao estado $ t $ na letra $ x $ então $ \ mathcal {g} $ terá estados $ s_1, s_2, t_1, t_2 $ e letra $ x $ vira $ s_1 $ para $ t_2 $ e $ s_2 $ para $ t_1 $ .

minha pergunta é por isso que é correto Aportach? $ \ mathcal {g} $ autômato não lê qualquer um dos $ v_1, v_3, v_5, ... v_ { k-1} $ então como ele pode garantir que esta palavra pertence a $ \ mathcal {l} $ ?

Answer 1

Deixe o PDA para a linguagem indicada $ l $ ser $ p $ . Tome duas cópias de de $ P $ : $ p_1 $ e < span class="contêiner matemático"> $ p_2 $ . Vamos juntar-se a $ p_1 $ e $ p_2 $ da seguinte forma: Se houver estado de transição $ S $ de $ t $ na leitura $ x $ Empurrando / Popping $ y $ , em seguida, adicione uma $ \ epsilon $ -transition de $ s_1 $ para $ t_2 $ empurrando / popping $ y $ e adicione uma transição de $ s_2 $ para $ t_1 $ na leitura $ x $ Empurrando / estourando $ y $ . Os estados iniciais estarão em $ p_1 $ e os estados finais em $ p_2 $ .

A ideia é: começamos a partir de um estado inicial em $ p_1 $ . Temos que fazer não-deterministicamente uma $ \ epsilon $ -transition (porque somente aqueles estão presentes quando estamos em um estado em $ P_1 $ ): Isso corresponderá à leitura $ v_1 $ . Então, quando estamos em um estado em $ p_2 $ , vamos ler $ v_2 $ e mover para Um estado apropriado em $ p_1 $ permitido pelas transições. Isso vai se certificar de que adivéssemos uma letra $ v_i $ antes de ler qualquer letra $ v_ {i + 1} $ A partir da entrada para toda $ i $ de $ 1 $ para $ k $ .
Isso vai se certificar de que $ v_1v_2 \ ldots $ está em $ l $ . Assim, apesar de estarmos apenas lendo cartas em posições mesmo, estamos adivinhando as cartas em posições ímpares, de modo que a palavra inteira deveria ter sido aceita por $ P $ . < / p >.

Você pode tentar provando formalmente isso.

Answer 2

Esta resposta assume que $ v_i \ in \ sigma $ são símbolos individuais.

Você pode provar isso usando propriedades de fechamento. A vantagem é que qualquer classe de idiomas fechada sob as propriedades de fechamento necessárias será fechada sob esta operação. Especificamente, precisaremos de encerramento sob homomorfismo, homomorfismo reverso e interseção com linguagem regular, que são exatamente o chamado "trio completo".

Deixe $ \ sigma '= {\ sigma': \ sigma \ in \ sigma \} $ ser uma cópia do recipiente de matemática $ \ Sigma $ . Definir homomorfismos $ r, d \ colon \ sigma \ cope \ sigma '\ to \ sigma $ por $ r (\ sigma )= r (\ sigma ')=sigma $ e $ D (\ sigma)=sigma $ , $ D (\ sigma ')=epsilon $ . Então $$ \ mathcal {g}= d (r ^ {- 1} (\ mathcal {l}) \ cap (\ sigma '\ sigma) ^ *). $$

Algumas famílias de línguas, por exemplo, linguagens sensíveis ao contexto, são fechadas sob o chamado "trio", no qual o homomofismo é substituído por $ \ epsilon $ -Free homomorfismo (significando $ h (\ sigma) \ neq \ epsilon $ para todas as letras $ \ sigma $ ).>). Podemos acomodar estes também com um argumento ligeiramente mais complicado.

Deixe $ e \ colon \ sigma '\ vezes \ sigma \ to \ sigma \ sigma $ ser dado por $ E (\ Sigma ', \ Sigma)=sigma' \ sigma $ , e deixe $ p \ colon \ sigma '\ times \ sigma \ to \ sigma $ ser dado por $ p (\ sigma ', \ sigma)=sigma $ . Então $$ \ mathcal {g}= p (e ^ {- 1} (r ^ {- 1} (\ mathcal {l}) \ cap (\ sigma '\ sigma) ^ *)). $$

Answer 3

As outras respostas Use Pushdown AutomatA e Propriedades de Encerramento. Vamos tentar uma solução com gramáticas sem contexto.

Podemos supor que $ l $ tem uma gramática livre de contexto em NormalForm Chomsky. O que significa que suas produções são da forma $ a \ para BC $ e $ a \ a $ , Com $ a, B, C $ nonterminais e $ a $ terminal (em $ \ sigma $ ).

Vamos construir uma gramática para a linguagem derivada $ g $ , onde cada outro símbolo é ignorado. A nova gramática terá nonterminais que acompanham a posição uniforme / ímpar do próximo terminal na string.

para cada nonterminal $ x $ Nós introduzimos quatro não-terminais $ [i, x, j] $ Com $ i, j $ $ 0 $ ou $ 1 $> $ 1 $ .

Para cada produção $ a \ para BC $ Nós introduzimos oito produções $ [i, A, K] \ para [i, b, j] [j, c, k] $

Para a produção do terminal de orelha $ a \ para um $ Nós introduzimos duas produções $ [0, A, 1] \ Para \ Varepsilon $ e $ [1, A, 0] \ para $ . (Essas produções alternaram a paridade do símbolo.)

O axioma para a nova gramática é $ [0, s, 0] $ onde $ s $ é o axioma original.

Esta construção realmente funciona da mesma forma que uma que pode ser usada para provar que os idiomas livres de contexto estão fechados sob interseção com idiomas regulares. Normalmente, que é mostrado usando o Pushdown AutomatA, mas pode ser feito com gramáticas sem contexto.