Análise LR(1)

Considere a gramática

1. Qual é a tabela da transição do autómato dos itens-LR(1) válidos?
2. Quais são os estados que têm itens completos?

N.B. Na tabela da transição do autómato dos itens-LR(1) válidos aplicam-se as seguintes convenções:

1. O estado inicial é .
2. Todos estados explicitamente indicados na tabela são finais.
3. Além dos estados explicitamente indicados o autómato tem mais um estado que não é final.
4. Sempre que não está explicitamente assinalado, o destino de uma transição é o estado não final referido acima.

Prefixos Viáveis LR(0)

Quais são as opções corretas de prefixos LR(0) viáveis e inviáveis da gramática acima?

Que Expressão Regular é equivalente ao seguinte Autómato Finito Não Determinista?

Indique qual é o Autómato Finito Determinista equivalente ao seguinte Autómato Finito Não Determinista:

Indique qual é o Autómato Finito Determinista Mínimo equivalente ao seguinte Autómato Finito Determinista:

Seja a linguagem das palavras sobre , não vazias, em que o primeiro símbolo e o segundo símbolos são iguais. Por exemplo, estão em enquanto que não estão.

Que Expressão Regular representa ?

Que Autómato Finito Não Determinista é equivalente à Expressão Regular ?

Que linguagem fica representada pela Expressão Regular ?

Neste exercício os Autómatos de Pilha são representados por tabelas

onde a primeira coluna indica o estado inicial e quais são finais e as restantes colunas definem as componentes da transição. Em cada linha

classifica o estado ; são estados de controlo; palavras na pilha e um símbolo na fita ou .

Note que podem ocorrer várias linhas para o mesmo .

Exercício: Qual é o Autómato de Pilha equivalente à Gramática Independente do Contexto ?

Indique qual é a Forma Normal de Greibach equivalente à gramática