INF05005/12-LSC

Em uma Gramática Sensível ao Contexto, a única restrição imposta ao formato das produções é:

• Lado esquerdo contém somente variáveis

• Não há restrição

• Comprimento do lado esquerdo sempre maior ou igual ao do lado direito

• Comprimento do lado direito sempre maior ou igual ao do lado esquerdo

Uma Gramática Irrestrita tem poder computacional equivalente a:

• Um Autômato Finito

• Um Autômato com Uma Pilha

• Um Autômato com Duas Pilhas

• Uma Gramática Sensível ao Contexto

Uma Linguagem Sensível ao Contexto é reconhecida por:

• Um Autômato com Pilha

• Uma Gramática de Livre de Contexto

• Um Autômato Linearmente Limitado

• Um Autômato com Pilha Determinístico

O conjunto de produções

S -> aA | b,

A -> BC | B,

aC -> BaA,

aA -> A,

bB -> Bb

segue o formato de:

• Uma GLC na FNG

• Uma GSC

• Uma Gramática Irrestrita

• Uma GSC e uma Gramática Irrestrita

É correto afirmar-se sobre LSC:

• Tem poder computacional igual ao de uma LRE

• É sempre recursiva

• Pode sempre ser descrita por uma GLC

• Serve apenas para questões sintáticas