Uma linguagem "simples" fora da ?

12

Estou procurando um idioma L com as seguintes propriedades:

L não deve ser livre de contexto.
O complemento de L não deve ser livre de contexto. (Tudo o que você vê nos livros didáticos como exemplos principais de linguagens sem contexto parece falhar neste segundo requisito.)
Por exemplo, eu sei que linguagens indecidíveis atendem aos dois primeiros requisitos, mas o que eu quero é uma linguagem mais simples que possa ser reconhecida por um modelo de autômato ligeiramente "aprimorado", por exemplo, um autômato de empilhamento probabilístico.

fl.formal-languages automata-theory Cem Say
fonte

15

Aqui está outro exemplo:

$\mathtt{L} = \{ x\#y \mid x \in \mathtt{EQ},y \in \overline{\mathtt{EQ}} \}$ ,
onde e são o complemento de . $\mathtt{EQ}=\{ a^nb^nc^n \mid n \geq 0 \}$ $\overline{\mathtt{EQ}}$ $\mathtt{EQ}$

É um fato bem conhecido que não está em . $\mathtt{EQ}$ $\mathsf{CFL}$

Suponha que seja reconhecido por um PDA . Nós construímos um novo PDA . Na entrada , simula na string . Como reconhece claramente , concluímos que . $\mathtt{L}$ $\small \mathcal{P_1}$ $\small \mathcal{P}'$ $w$ $\small \mathcal{P}'$ $\small \mathcal{P}_1$ $w\#a$ $\small \mathcal{P}'$ $\mathtt{EQ}$ $\mathtt{L} \notin \mathsf{CFL}$

Da mesma forma, suponha que o complemento de seja reconhecido por um PDA . Nós construímos outro PDA . Na entrada , simula na string . também reconhece , portanto também não pode estar em . $\mathtt{L}$ $\small \mathcal{P}_2$ $\small \mathcal{P}''$ $w$ $\small \mathcal{P}''$ $\small \mathcal{P}_2$ $\#w$ $\small \mathcal{P}''$ $\mathtt{EQ}$ $\mathtt{L}$ $\mathsf{coCFL}$

$\mathtt{EQ}$ pode ser reconhecido por um autômato probabilístico (unidirecional) de balcão único (P1CA) com qualquer erro desejado vinculado ( Freivalds, 1979 ). Portanto, não é difícil mostrar que também pode ser reconhecido por um P1CA com qualquer erro desejado. $\mathtt{L}$

Abuzer Yakaryilmaz
fonte

Ainda melhor que a resposta de Dominik, pois também descreve um PPDA que reconhece o idioma! (Dominik de é uma linguagem de registro, e não tenho idéia de como construir um PPDA que é superior a um PDA sobre uma linguagem de registro.)

Cem Say

@CemSay: PPDAs também não conseguem reconhecer nenhuma linguagem não regular com erros limitados, Kaneps et al.

Abuzer Yakaryilmaz

22

Que tal ? É fácil ver que e seu complemento não são regulares e, portanto, (como estamos lidando com um alfabeto unário), não são livres de contexto. $L:=\{a^{n^2}\mid n\in\mathbb{N}\}$ $L$

Dominik D. Freydenberger
fonte

É isso, obrigado. Isso é o que minha pergunta pediu, por isso estou aceitando, mas gostaria muito de receber outros exemplos.

Cem Diga

4

$QSAT$ ou mesmo são exemplos, a menos que ou respectivamente. é um exemplo, uma vez que é -completo e . $SAT$ $P = PSPACE$ $P = NP$ $SAT$ $NP$ $CFL \subseteq P$

$QSAT$ (fórmulas booleanas quantificadas verdadeiras) é completo no e é um CSL, reconhecível por um LBA. $PSPACE$

Para exemplos incondicionais, você pode pegar um problema arbitrário completo de , como xadrez generalizado ou Go. $EXP$

Mike B.
fonte

Sim, obrigado, mas ainda mais simples, de preferência os da classe P, por favor?

Cem Diga

Uma linguagem "simples" fora da ?

Respostas: