Алфавит - это конечный непустой набор символов. Строка над алфавитом, для наших целей, представляет собой конечную последовательность символов из этого алфавита. Для наших целей язык - это набор строк над этим алфавитом.
Грамматика для наших целей - это набор правил, называемых продукцией, которые определяют язык, описывая, как могут строиться строки на этом языке. В качестве примеров можно привести регулярные грамматики, контекстно-свободные грамматики и неограниченные грамматики.
Автомат для наших целей - это набор правил, называемых переходами, которые определяют язык, описывая, как строки в этом языке могут быть распознаны. Конечные автоматы, автоматы сжатия и машины Тьюринга - примеры.
Регулярные выражения - это специальная запись для представления регулярных языков. Они похожи на регулярные грамматики и конечные автоматы в том смысле, что они определяют регулярные языки.
Первая задача компиляторов - обработать ввод, чтобы определить, допустим ли ввод. Для этого компилятор проверяет, является ли ввод допустимой строкой на языке (набор строк) всех допустимых входных данных (списки исходного кода программы на целевом языке программирования). Этот язык (набор строк) определяется грамматикой (которая определяет язык программирования), и компилятор реализует автомат (обычно компилятор может использовать все что угодно, вплоть до возможностей уровня TM, но для производительности и простоты обычно ограничивает себя к контекстно-свободным или в большинстве контекстно-зависимых функций). Компьютер «распознает» конечные автоматы в том смысле, что компьютер работает так, что делает его очень хорошим в выполнении того, что предлагают наши диаграммы, так же, как диаграммы предлагают это.