Exercícios — Gramáticas e Autómatos de Pilha

Os exercícios assinalados com "✓" serão resolvidos nas aulas práticas; Os assinalados com "†" têm elevada dificuldade. Todos os restantes devem ser resolvidos pelos alunos.

• Exercícios — Gramáticas e Autómatos de Pilha
  • Gramáticas Independentes do Contexto
    • Exercício 01
    • Exercício 02
    • Exercício 03
    • Exercício 04
    • Exercício 05
    • Exercício 06
    • Exercício 07
    • Exercício 08
    • Exercício 09
    • Exercício 10
    • Exercício 11
    • Exercício 12
  • Autómatos de Pilha
    • Exercício 13
    • Exercício 14
    • Exercício 15
    • Exercício 16
    • Exercício 17
    • Exercício 18
  • Implementação
    • Uma biblioteca para GIC e AP
    • Exercício 19

Gramáticas Independentes do Contexto

Exercício 01

Escolha três ou quatro linguagens de programação (como C, python, Java ou outras mais recentes como go ou swift) ou apenas formais (como o XML) e encontre (online) gramáticas que as definam.

Exercício 02

Defina uma gramática independente do contexto que gere a linguagem:

1. $\left\{wc{w}^R:w\in {\left\{a,b\right\}}^{\ast }\right\}$.
2. $\left\{w{c}^n:w\in {\left\{a,b\right\}}^{\ast }\text{ e }n=\left|w\right|\right\}$.
3. $\left\{a^i{b}^j{c}^k:k\ge 0\text{ e }i+j=k\right\}$.
4. ✓ $\left\{a^n{b}^m:m,n\ge 0\text{ e }m\ne n\right\}$.
5. dos números naturais sem zeros não significativos.

Exercício 03

Defina uma gramática independente do contexto que gere os reais (incluindo os negativos) em que: a parte inteira é não vazia e não tem zeros não significativos; a parte decimal é não vazia e só termina em zero se for constituída por um único 0; e as partes inteira e decimal são separadas por uma vírgula.

Exercício 04

✓ Seja $L$ a linguagem de todas sequências de parêntesis, curvos - ‘$($’ e ‘$)$’ - e rectos - ‘$[$’ e ‘$]$’ -, bem emparelhados. Pertencem a esta linguagem palavras como $\lambda$, “$()$”, “$[]$”, “$()[()]$”, “$([()])$” e “$([][([])])[]$”. Não pertencem a $L$ palavras como “$]$”, “$($”, “$(]$”, “$([)]$”, “$)($” e “$[()]]$”.

1. Mostre que $L$ não é regular;
2. Defina uma gramática independente do contexto que gere $L$.

Exercício 05

✓ Considere um conjunto $V$ de variáveis e um conjunto $F$ de símbolos de função, cada um com uma aridade maior que ou igual a zero. Um termo é definido como:

• uma variável é um termo.
• um símbolo de função de aridade 0 é um termo.1
• se $t_1,t_2,\dots ,t_k,k>0$ são termos, então, para todos os símbolos de função $f$ de aridade $k$, $f\left(t_1,t_2,\dots ,t_k\right)$ é um termo;
• nada mais é um termo.

Defina uma gramática independente do contexto que gere os termos descritos — use os símbolos $v$ e $f$ como representantes das variáveis e dos símbolos de função, respetivamente. Exemplos de termos são $v$, $f$, $f(v)$ e $f(v,f(f(f),f))$.

Exercício 06

Considere a gramática $G=\left(\left\{A\right\},\left\{a,b\right\},\left\{A\to AA|aAb|\lambda \right\},A\right)$.

1. Construa uma derivação esquerda para a palavra $aababb$ e a respetiva árvore de derivação.
2. Construa uma derivação direita para a palavra $ababab$ e a respetiva árvore de derivação.
3. Determine se G é ambígua. † Em caso afirmativo, apresente uma gramática não ambígua equivalente.

Exercício 07

✓ Considere a gramática independente do contexto $$G=\left(\left\{S\right\},\left\{a\right\},\left\{S\to aa|SS\right\},S\right).$$

1. Mostre que esta gramática é ambígua.
2. † Apresente uma gramática equivalente não ambígua.
3. Apresente uma gramática regular equivalente.
4. Apresente uma expressão regular que represente a linguagem gerada pela gramática.

Exercício 08

Resolva o exercício anterior para a gramática $$G=\left(\left\{S,A\right\},\left\{a\right\},\left\{S\to \lambda |AS,A\to \lambda |a\right\},S\right).$$

Exercício 09

Defina uma gramática livre do contexto que gere a linguagem …

1. $\left\{0^{2k}{1}^{k-1}:k\ge 1\right\}$. Usando essa gramática, derive a palavra $00001$.
2. $\left\{1^{2k+1}{0}^k:k\ge 0\right\}$. Usando essa gramática, derive a palavra $1110$.

Exercício 10

† Defina uma gramática livre do contexto que gere todas a expressões regulares sobre o alfabeto $\left\{a,b\right\}$.

Exercício 11

Considere a gramática livre do contexto $S\to aSaa|B;B\to bbBcc|C;C\to bc$

1. Derive $a^3{b}^3{c}^3{a}^6$.
2. † Mostre que esta gramática é não ambígua.

Exercício 12

Considere a gramática livre do contexto $S\to AaSbB|\lambda ;A\to aA|a;B\to bB|\lambda$;

1. Mostre que esta gramática é ambígua.
2. Encontre uma gramática equivalente, não ambígua.

Autómatos de Pilha

Exercício 13

✓ Defina um autómato finito que reconheça a linguagem gerada pela gramática $S\to 01S|0S|11|1$.

Exercício 14

✓ Defina um autómato de pilha que reconheça a linguagem $\left\{w:w\in {\left\{a,b\right\}}^{\ast }\text{ e }w=w^R\right\}$. Será possível definir um autómato de pilha determinista que reconheça esta linguagem? Justifique a sua resposta.

Exercício 15

✓ Considere a linguagem de todas as palavras sobre $\left\{a,b\right\}$ em que o número de $a$ é igual ao número de $b$:

$$\left\{p\in {\left\{a,b\right\}}^{\ast }:{\left|p\right|}_a={\left|p\right|}_b\right\}$$

1. defina um autómato de pilha não determinista que a reconheça.
2. † defina um autómato de pilha determinista que a reconheça.

Exercício 16

Defina um autómato de pilha que reconheça $L=\left\{1^n+1^m=1^{m+n}:n,m\ge 0\right\}$ e indique se esse autómato é, ou não, determinista.

Exercício 17

Defina um autómato de pilha que reconheça $L=\left\{a^{2n}{b}^{3n}:n\ge 0\right\}$.

Exercício 18

Construa um autómato de pilha que reconheça a linguagem das expressões aritméticas com o operador $+$ e com parêntesis. Use o símbolo $n$ para representar os operandos atómicos, i.e., as expressões terão o seguinte aspeto: $n$, $n+n$, $(n+(n+(n)))+n$, etc.

Implementação

As indicações gerais para os exercícios de implementação são válidas aqui.

Uma biblioteca para GIC e AP

Para esta biblioteca são adotadas as seguintes convenções e orientações:

1. Um símbolo é uma string válida: uma string não vazia em que não ocorre ' '.
2. Uma variável é um símbolo que começa por uma maiúscula.
3. Um terminal é um símbolo que não é uma variável.
4. Estão implementadas funções is_symbol(s), is_variable(s) e is_terminal(s).
5. Uma palavra é uma lista de símbolos.
6. As regras são representadas pela classe Rule, com:
   1. O construtor Rule(var, word).
   2. Os métodos básicos variables(), terminals(), equals(other).
   3. Os métodos analíticos is_nil(), is_recursive(), is_wellformed().
   4. Os métodos operacionais dderive_left(word), dderive_right(word).
   5. O método auxiliar __repr__() com "→" para a seta e usando "λ" quando adequado.
   6. A função auxiliar parse_grammar(s). Assume-se que s é uma string com os símbolos separados por espaços, que o primeiro desses símbolos define o lado esquerdo da regra e os restantes a palavra do lado direito. Por exemplo, "A a A b" define a regra A→aAb.
7. As gramáticas são representadas pela classe Grammar, com:
   1. O construtor Grammar(rules).
   2. Os métodos básicos variables(), terminals(), rules_of(symbol) e set_start(symbol).
   3. Os métodos analíticos is_wellformed(), start() (o símbolo inicial), is_nil(symbol), nil_symbols(), is_recursive(symbol), recursive_symbols().
   4. Os métodos operacionais derive_left(sequence, word), derive_right(sequence, word) onde sequence é uma lista com indíces das regras e word é um parâmetro opcional com valor por omissão igual ao símbolo inicial da gramática (start()).
   5. O método auxiliar __repr__().
   6. A função auxiliar parse_grammar(s). Assume-se que s é uma string com blocos de regras separados por ';' e em que cada bloco de regras é da forma V : P1 | P2 | ...| Pn. Por exemplo "S:a A b|;A:S|c" define a gramática $S\to aAb|\lambda ;A\to S|c$. Note bem que as regras de uma variável podem estar "espalhadas" por vários blocos e que eventuais repetições de regras devem ser descartadas.
8. O símbolo inicial (start) de uma gramática é calculado da seguinte forma:
   1. Se for usado o método set_start(symbol) é o valor do parâmetro symbol.
   2. Caso contrário, se 'S' é uma variável na gramática ou se a gramática tem zero regras, o símbolo inicial é 'S'.
   3. Por fim, se nenhuma das outras situações se verifica, é o lado esquerdo da primeira regra da gramática.
9. As linhas das transições, $(q_1,s_1)\in \delta (q_0,a,s_0)$, são representadas pela classe TrLine, com:
   1. O construtor TrLine(state_0, symbol, stack_0, state_1, stack_1) onde (state_0, symbol, stack_0, state_1, stack_1) é $(q_0,a,s_0,q_1,s_1)$.
10. As configurações, $(q,p,s)$, são representadas pela classe Configuration, com:
    1. O construtor Configuration(state, tape, stack) onde (state, tape, stack) é $(q,p,s)$.
    2. Os métodos analíticos is_final(final_symbols), is_fitting(trline) e all_fitting(transition).
    3. Os métodos operacionais next(trline, check) e tree(delta, max_depth, check) em que check é um parâmetro opcional que por omissão vale False e, sendo verdadeiro, ativa a verificação is_fitting(trline). Note bem que o resultado de aplicar uma linha a uma configuração incompatível é a configuração inicial.

Exercício 19

Sempre que possível teste a sua biblioteca com as gramáticas e os autómatos dos exercícios anteriores.