План лекции:
Способы описания формальных языков:
- словесное
- теоретико-множественное
- с помощью допускающих автоматов (допускающих программ)
- регулярные выражения
- грамматики
- контекстно-свободные грамматики
- вложенность множества регулярных языков в множество контекстно-свободных языков
Счетность множества всех слов в алфавите {0,1}, несчетность множества всех языков в алфавите {0,1}.