Courses‎ > ‎

Aviso 30/09

A aula do dia 30/09 está cancelada. A partir da próxima aula, o Prof. Luerbio volta a dar as aulas.

Agradeço a oportunidade de trabalhar com vocês.

Gostaria que anexassem o seguinte conteúdo ao material escrito de vocês, que ficou faltando no fim da última aula:

  • Terminamos a aula fazendo uma gramática G3 que, do jeito que ficou em sua última versão, reconhecia a linguagem {xx | x é uma cadeia sobre {a, b} e |x| > 0 }. Pedi a vocês que pensasse sobre como incluir a cadeia vazia à linguagem de G3, que era a proposta da linguagem original. Pedi que refletissem se adicionar a regra S --> epsilon era suficiente. A resposta é SIM.

  • Notem que a gramática G3, sem a alteração acima, é sensível ao contexto, mas não é livre de contexto, nem regular. Existiria alguma gramática regular ou livre de contexto que reconhecesse {xx | x é uma cadeia sobre {a, b} e |x| > 0 }? Como informação, a resposta é NÃO. Mais a frente, dependendo do foco que o Prof. Luerbio dará, uma ferramenta para chegar a esta conclusão será apresentada.

  • Existem outros nomes para as gramáticas. Acho que o Prof. Luerbio prefere estes outros nomes. Por via das dúvidas, segue outra nomemclatura:
    • gramáticas (sem restrições): Tipo 0
    • gramáticas sensíveis ao contexto: Tipo 1
    • gramáticas livres de contexto: Tipo 2
    • gramáticas regulares: Tipo 3
Comments