As linguagens livres de contexto podem ser obtidas como o fechamento da linguagem Dyck nas operações do cone . A linguagem Dyck é uma linguagem livre de contexto determinístico, e as operações de cone correspondem às operações que podem ser implementadas por transdutores de estado finito não...
De um comentário , uma pergunta interessante surgiu. A classe de CFLs (os idiomas reconhecidos pelos PDAs) obviamente não está fechada sob não-determinismo - o que quero dizer com isso é que os PDAs determinísticos não são equivalentes em poder aos PDAs não-determinísticos. No entanto, todas as...
Alguém pediu exemplos de linguagens sem contexto com complementos sem contexto . A primeira resposta diz: O idioma eu1 1= { w w ∣ w ∈ { a , b}∗}eu1 1={WW∣W∈{uma,b}∗}L_1= \{ww \mid w \in \{a,b\}^*\}não é livre de contexto (como pode ser mostrado usando o lema de bombeamento; veja aqui ). Seu...
Para um idioma LLL, definir: NE(L)={x∈L:x is not the proper prefix of any string in L}NE(L)={x∈L:x is not the proper prefix of any string in L} NE(L) = \{x \in L : x \text{ is not the proper prefix of any string in } L\} Estou tentando mostrar que as linguagens sem contexto não estão fechadas...
L = { ϵ }L={ϵ}L = \left \{ \epsilon \right \} Claramente, esse idioma é finito, portanto deve ser um idioma regular. Agora, como toda linguagem comum é sensível ao contexto,euLLé uma CSL. Podemos definir a gramática paraeuLL Como : S→ ϵS→ϵS\rightarrow \epsilon Agora desde euLLé uma CSL, essa...
Eu tenho procurado uma linguagem prototípica para linguagens recursivas (decidíveis) que não seja sensível ao contexto sem sucesso. Por exemplo, é prototípico de linguagens regulares, para linguagens livres de contexto e para linguagens sensíveis ao contexto. Eu costumo considerar a linguagem que é...
Vai L={a∗b∗}L={a∗b∗}L = \{a^* b^*\} ser classificado como um idioma regular? Estou confuso porque sei que L={anbn}L={anbn}L = \{a^n b^n\}não é regular. Que diferença faz a estrela
O objetivo de Turing ao construir seu conceito era formalizar como os humanos fazem o raciocínio abstrato. Agora me corrija se eu estiver errado, mas esse raciocínio parece apenas um exercício em que você manipula um conjunto de declarações formais, ou seja, strings sem nenhuma semântica associada...
Eu estive mexendo com esse problema durante a última hora e estou incrivelmente perplexo. Seja . Mostre que é regular.A={0ku0k∣k≥1 and u∈Σ∗}A={0ku0k∣k≥1 and u∈Σ∗}A = \{\; 0^ku0^k \mid k ≥ 1 \text{ and }u ∈ Σ^*\;\}AAA Obviamente, a linguagem satisfaz o lema de bombeamento, mas isso não é...
Atualmente, estou estudando línguas formais. Minha palestra afirma que, embora as palavras de uma língua sejam finitas, as frases construídas com a gramática subjacente não são. Mas não entendo por que isso geralmente deve ser verdade. Eu posso imaginar a gramática que me deixa com uma quantidade...
O algoritmo de Brzozowki é amplamente citado. Várias perguntas aqui dão exemplos ou discutem sua complexidade. Mas não consegui encontrar uma prova de correção para o algoritmo. Como provamos que está correto? Qualquer prova acessível aos estudantes de ciências da computação seria muito...