10. Considere a seguinte propriedade sobre uma linguagem formal L: ¿Existe um número natural n ≥ 0, tal que para qualquer palavra w ∈ L:
1. Todo z ...
10. Considere a seguinte propriedade sobre uma linguagem formal L: ¿Existe um número natural n ≥ 0, tal que para qualquer palavra w ∈ L: 1. Todo z ∈ L com z ≥ n pode ser escrito como w=uvwxy, para algumas cadeias u,v,w,x,y. 2. |vx| ≥ 1 3. |vwx| ≤ n 4. uvkwxky ∈ L para todo k ≥ 0 Com base no enunciado e nos conhecimentos sobre o tema, atribua V (verdadeiro) ou F (falso) para as afirmativas a seguir. ( ) Se L é aceita por PDA, então L satisfaz a propriedade acima. ( ) L = {0p; onde p é primo} não satisfaz a propriedade acima. ( ) A propriedade acima é falsa para a linguagem L = {WcWR | W ∈ (a, b)*} ( ) A linguagem {anbncn; n ≥ 0} não satisfaz a propriedade acima. ( ) O lema do bombeamento para linguagem livre de contexto é usado para provar que certos conjuntos são livres de contexto. Assinale a alternativa que contém, de cima para baixo, a sequência correta:
Se L é aceita por PDA, então L satisfaz a propriedade acima. L = {0p; onde p é primo} não satisfaz a propriedade acima. A propriedade acima é falsa para a linguagem L = {WcWR | W ∈ (a, b)*} A linguagem {anbncn; n ≥ 0} não satisfaz a propriedade acima. O lema do bombeamento para linguagem livre de contexto é usado para provar que certos conjuntos são livres de contexto. V, V, F, V, F. F, V, F, V, V. V, V, F, V, F. V, F, V, F, F. F, V, V, F, V.
Compartilhar