Linguagens Formais e Automata

Primeiro trimestre de 2009

Horário: alfa (4ª 8-10, 6ª 10-12)

Sala de aula: S 504 (bloco B)

Sala do professor: S 805 (bloco B)

Email do professor: jeronimo.pellegrini ufabc edu br

Novidades:

18/05 -- CONCEITOS FINAIS
18/05 -- Notas da lista 13
18/05 -- Notas da prova 2 disponíveis
18/05 -- Questão 7 da primeira seção do Jung (da lista 13) anulada
16/05 -- Notas das listas atrasadas (12)
09/05 -- Pequeno erro na lista 13 corrigido (onde se lia ``(λ • y axa)'', agora se lê ``(λ y • axa)''
08/05 -- Notas da lista 11
08/05 -- Notas da lista 12
08/05 -- Lista 12 teve um exercício cancelado
07/05 -- Mais duas notas da lista 5 (estavam por corrigir)
02/05 -- Lista 13 disponível
02/05 -- Indicação de leitura (tutorial de λ-cálculo de Raúl Rojas)
01/05 -- Indicação de leitura (Arora/Barak, capítulo sobre Computação Quântica)
01/05 -- Indicação de leitura (tutorial de λ-cálculo de Achim Jung)
25/04 -- Link para gerador de imagens a partir de gramáticas livres de contexto
16/04 -- Prazo da lista 12 adiado (1º de Maio é feriado!)
16/04 -- Cronograma alterado: 1º de Maio é feriado!
16/04 -- Lista 12 disponível
16/04 -- Notas remanescentes de listas atrasadas já computadas
16/04 -- Notas da lista 5
15/04 -- Notas da lista 10
15/04 -- Programa do curso mudou (Computabilidade Quântica incluída)
15/04 -- Mais indicações de livros (bibliografia secundária, Lanzagorta/Uhlmann e Marinescus)
11/04 -- Notas da lista 9
11/04 -- A partir de agora, lista com atraso tem desconto!
10/04 -- Lista 11 disponível
09/04 -- Notas da prova disponíveis
31/03 -- QUEM QUISER REFAZER AS LISTAS 6 E 8 PODERÁ FAZÊ-LO UMA VEZ!
30/03 -- Lista 10 disponível
30/03 -- Lista 5 adiada novamente
30/03 -- Notas da lista 8
30/03 -- Mais uma indicação de livro (bibliografia secundária, Aho/Sethi/Ullman/Lam)
27/03 -- Média das listas já corrigidas adicionadas à tabela de notas
27/03 -- Notas da lista 7
27/03 -- Notas da lista 6
27/03 -- Notas da lista 4
26/03 -- Textos sobre análise sintática disponíveis (link na seção de bibliografia principal)
26/03 -- Mais uma indicação de livro (bibliografia secundária, livro do Louden)
20/03 -- Notas da lista 3
18/03 -- Prazo do exercício 5 extendido
17/03 -- Lista 9 disponível
17/03 -- Notas das listas já entregues disponíveis
16/03 -- Lista 8 (FÁCIL: refazer exercício feito em sala) disponível
13/03 -- MAIS UM LIVRO NA BIBLIOTECA (e na bibliografia principal): Lewis & Papadimitriou
12/03 -- Lista 7 disponível
11/03 -- Lista 6 disponível
11/03 -- Lista 4 reestruturada, lista 5 disponível
06/03 -- Lista de exercícios 4 disponível
27/02 -- O LIVRO DO SIPSER (EM PORTUGUÊS) ESTÁ DISPONÍVEL NA BIBLIOTECA! (Comemorem!)
27/02 -- Lista de exercícios 3 disponível
12/02 -- Primeiras listas de exercicios disponíveis

Assuntos Relacionados

Context Free Art

Alguém encontrou uma forma de produzir imagens (algumas bastante interessantes) usando gramáticas livres de contexto! Vejam o Context Free Art (tem um programinha para baixar e usar em casa -- vocês mesmos podem criar gramáticas para gerar imagens).

Ementa

Linguagens Regulares. Linguagens Livres de Contexto. Linguagens Enumeráveis Recursivamente e Sensíveis ao Contexto. Hierarquia de Chomsky. Indecidibilidade.

Avaliação

Há três notas:

Uma nota final será composta da seguinte forma:

N = (E + 3P1 + 4P2 / 8)
O conceito final na disciplina será dado por:

Exercícios

TODOS OS EXERCÍCIOS DEVEM SER MANUSCRITOS, SEM O USO DE IMPRESSORA!

Em todas as listas, façam apenas os exercícios que não estão já respondidos no livro.

A partir da lista 11, entregas atrasadas terão desconto!

Notem: × = entregue ecorrigido. ∗ = entregue, ainda não corrigido.

  1. × Exercícios (e problemas) do Capítulo 0 do Sipser (segunda edição) -- somente os que não vem com resposta no livro. Prazo: 27/02
  2. × Exercícios do Capítulo 0 do Carroll/Long (Somente 0.13, 0.24--0.27, 0.29--0.31). Prazo: 04/03
  3. × Exercícios 1.4--1.6, 1.12, 1.31--1.33 e problema 1.45 do capítulo 1 do Sipser. Prazo: 13/03
  4. × Exercícios 1.14 e 1.15, e problemas 1.34-1.36 do capítulo 1 do livro do Sipser, 6.3--6.5 e 6.43 de Carroll/Long, 37, 38, 39 e 41 do capítulo 1 do livro do Xavier. Prazo: 18/03
  5. × Seja o operador c tal que, para quaisquer linguagens A e B, c(A,B) = {w | w ∈ A, ∃ w' ∈ B tal que |w| = |w'|} ∪ {w | w ∈ B, ∃ w' ∈ A tal que |w| = |w'|}.
    Descreva informalmente o conjunto c(A,B), e prove que as linguagens regulares são (ou que não são) fechadas sob a operação c. Prazo: 20/03 04/04 15/04
  6. × Faça o problema 1.46 do capítulo 1 do Sipser. Prazo: 25/03
  7. × Faça os problemas 1.53, 1.55, 1.63 do capítulo 1 do Sipser. Prazo: 25/03
  8. × Em sala de aula, vimos a prova de que L não é regular, onde L = { an | n é primo }. Refaça a prova, cuidadosamente e com muita clareza. Você pode usar o seguinte fato (no enunciado, todas os números são inteiros ≥ 0): ∀ c, não existem a, b tais que: (basta tomar k = 2a e verificar -- inclua isto em sua prova!)
    Atenção: nesta questão você deve mostrar que consegue expressar claramente, de maneira simples porém rigorosa o raciocínio (que já vimos em sala). Não complique a prova, tenha certeza que o raciocínio está claro e fácil de seguir. Prazo: 27/03
  9. × Faça os exercícios 3.1.2, 3.1.3, 3.1.5 e 3.1.9 do capítulo 3 do Lewis & Papadimitriou. Prazo: 01/04
  10. × Faça os exercícios 4.4.3, 4.4.4 e 4.5.3 do Aho/Sethi/Ullman/Lam.
    ♦ Ao fazer o exercíco 4.5.3, mostre a configuração (pilha + símbolos a serem lidos) em dois momentos, um deles na iminência de uma redução e outro na iminência de um deslocamento.
    ♦ Use a definição de FIRST e FOLLOW que ele dá no livro, ou a de φ e Δ dada nas notas de aula que deixei neste site. Prazo: 15/04
    ♦ Quando ele pede ``give bottom-up parses'', isto significa todo o processo de parsing (passo a passo).
  11. × Faça o exercício 3.8 e o problema 3.14 do Capítulo 3 do Sipser. Prazo: 22/04 Após o prazo haverá desconto na nota!
  12. × Faça o exercício 5.4 e os problemas 5.13, 5.17 e 5.24 do Capítulo 5 do livro do Sipser e o exercício 9.3.2 do livro do Aho. Prazo: 01/05 06/05
    Na verdade era para ser o exercício do Hopcroft; como errei e disse "Aho", esta parte da lista está cancelada.
  13. × (Esta lista é fácil!) Prazo: 13/05 (dia da prova) -- MAS RECOMENDO TENTAR FAZER E TIRAR DÚVIDAS MUITO ANTES DISSO!
    1. Ache a forma normal dos termos (é mais fácil se você der nomes a subtermos):
      1. (λ e • eue) (abc)
      2. (((λ x • (λ y • axa)) q) r)
      3. (λ a • (λ x • xaux)) (λ y • yy)
    2. Determine os tipos dos termos e dos átomos cujos tipos não estão especificados:
      1. (λ w:CHAR • x:INT)
      2. (λ x:INT • (λ u:INT • a:CHAR))
      3. (λ x:CHAR • (λ u:INT • a:INT)) (λ j:INT • k)
    3. O tutorial do Jung tem duas pequenas listas de exercícios (seções 8 e 15). Faça os exercícios 2, 3, 4 e 7 da seção 8 e o exercício 4 da seção 15. Ponto extra para quem dizer o exercício 8 da seção 8.
    4. Descreva uma gramática que gere infinitos λ-termos sem forma normal. Prove que qualquer palavra gerada por sua gramática é um λ-termo sem forma normal.
    5. Mostre que o λ-cálculo pode gerar linguagens livres de contexto.

Notas

Notem: como eu havia mencionado, a parte final da disciplina é mais difícil e precisa de mais dedicação. Este certamente é o motivo da queda na média das notas da P1 para a P2.

Veja as notas das listas e provas até agora.

Programa aproximado

Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer.

Bibliografia

Principal

Tentaremos usar principalmente o livro do Michael Sipser, mas em alguns momentos usaremos outros livros.

Peguem as erratas dos livros nos sites dos autores!

Há também dois textos sobre análise sintática, usados em um curso na Unicamp em 2000. Um sobre análise descendente e outro sobre análise ascendente. Estes são para ler devagar.

Secundária