Лекция 2 (2010-09-08)

План лекции:

Способы описания формальных языков:

  • словесное
  • теоретико-множественное
  • с помощью допускающих автоматов (допускающих программ)
  • регулярные выражения
  • грамматики
    • контекстно-свободные грамматики
    • вложенность множества регулярных языков в множество контекстно-свободных языков

Счетность множества всех слов в алфавите {0,1}, несчетность множества всех языков в алфавите {0,1}.

Leave a Reply