Perguntas sobre o conjunto de idiomas (equivalente) descrito pelas gramáticas sem contexto ou aceito pelos autômatos de empilhamento (não determinísticos).
Existem muitas definições on-line sobre o que é uma gramática livre de contexto, mas nada que eu encontre satisfaça meu principal problema: De que contexto é livre? Para investigar, pesquisei no Google "gramática sensível ao contexto", mas ainda não consegui encontrar o que era o...
Eu estudo os compiladores há algum tempo e tenho pesquisado o que significa "contexto" na gramática e o que significa que a gramática é "livre de contexto", mas sem resultado. Então, alguém pode ajudar com
Eu tenho um conjunto de pares. Cada par tem a forma (x, y) tal que x, y pertencem a números inteiros do intervalo [0,n). Portanto, se n é 4, tenho os seguintes pares: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Eu já tenho os pares. Agora, eu tenho que construir uma combinação usando n/2pares de...
Existem muitas técnicas para provar que uma linguagem não é livre de contexto, mas como posso provar que uma linguagem é livre de contexto? Que técnicas existem para provar isso? Obviamente, uma maneira é exibir uma gramática sem contexto para o idioma. Existem técnicas sistemáticas para encontrar...
O seguinte contexto de linguagem é livre? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Conforme apontado por sdcvvc, uma palavra nesse idioma também pode ser...
Meu problema é como posso provar que uma gramática é inequívoca? Eu tenho a seguinte gramática: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression...
Dada uma gramática livre de contexto G, existe um autômato de empilhamento não determinístico N que aceita exatamente o idioma que G aceita. (e vice-versa) Também pode existir um autômato de empilhamento determinístico D que aceite exatamente o idioma que G também aceita. Depende da...
Ao considerar os modelos de máquinas computacionais, a hierarquia de Chomsky é normalmente caracterizada por (em ordem), autômatos finitos, autômatos push-down, autômatos de ligação linear e Máquinas de Turing. Para o primeiro e o último nível 1 (linguagens regulares e linguagens recursivamente...
As linguagens sem contexto não são fechadas sob complemento, sabemos disso. Tanto quanto eu entendo, linguagens sem contexto que são um subconjunto de para algumas letras estão fechadas no complemento (!?)a∗b∗a∗b∗a^*b^*a,ba,ba,b Aqui está o meu argumento. Cada linguagem CF tem uma imagem Parikh...
Vamos considerar duas gramáticas livres de contexto e e fazer a seguinte pergunta: É , isto é, são as duas gramáticas equivalente?G1G1G_1G2G2G_2L ( G1) = L ( G2)eu(G1)=eu(G2)L(G_1) = L(G_2) Em geral, esse problema é indecidível. No entanto, se ambos e lineares esquerda são (ou lineares direita)...
Existe um algoritmo / procedimento sistemático para testar se uma linguagem é livre de contexto? Em outras palavras, dado um idioma especificado em forma algébrica (pense em algo como ), teste se o idioma é livre de contexto ou não . Imagine que estamos escrevendo um serviço da Web para ajudar os...
Uma gramática livre de contexto pode incluir "estados mortos" de um autômato, como G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,? As regras de produção e se sempre e nunca geram...
Diz-se que a interseção de uma linguagem livre de contexto L com uma linguagem regular M é sempre livre de contexto. Entendi a prova de construção entre produtos, mas ainda não entendo por que ela é livre de contexto, mas não regular. O idioma gerado por essa interseção possui seqüências de...
Observe que esta é uma pergunta relacionada ao estudo em um curso de CS em uma universidade, NÃO é tarefa de casa e pode ser encontrada aqui no exame do outono de 20112. Aqui estão as duas perguntas de um exame passado. Eles parecem estar relacionados, o primeiro: Deixei F I N I T EC F G= {...
Gostaria de saber se isso é possível, já que . Portanto, um PDA que pode distinguir uma palavra do resto de pode aceitá-la , o que me parece contraditório. w ∈ { um n b n c n | n ≥ 0 } { um * b * c * }{anbncn∣n≥0}∉CFL{anbncn∣n≥0}∉CFL\{a^n b^n c^n \mid n \geq 0\} \not\in...
Portanto, basicamente L satisfaz as condições do lema de bombeamento para CFLs, mas não é uma CFL (isso é possível de acordo com a definição do
Seja uma gramática livre de contexto. Uma série de terminais e não terminais de é dito ser uma forma sentencial de se você pode obtê-lo através da aplicação de produções de zero ou mais vezes para o símbolo de início de . Vamos ser o conjunto de formas de sentenciais .GGGG G S SF ( G )...
Eu sei que existem linguagens não regulares, de modo que é regular, mas todos os exemplos que posso encontrar são sensíveis ao contexto, mas não livres de contexto.eu∗eu∗L^* Caso não exista, como você prova
Estou tentando entender o que se entende por "determinístico" em expressões como "gramática determinística livre de contexto". (Existem "coisas" mais determinísticas neste campo). Eu apreciaria um exemplo mais do que a explicação mais elaborada! Se possível. Minha principal fonte de confusão é não...
Defina o idioma como . Em outras palavras, contém as palavras que não podem ser expressas como algumas palavras repetidas duas vezes. é livre de contexto ou não?LLLL={a,b}∗−{ww∣w∈{a,b}∗}L={a,b}∗−{ww∣w∈{a,b}∗}L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}LLLLLL Tentei cruzar com , mas ainda não posso...