Определение 2.5.1. Праволинейная грамматика в нормальной форме (автоматная грамматика, регулярная грамматика, finite -state grammar) - это праволинейная грамматика, в которой каждое правило имеет вид , , или , где , , .
Теорема 2.5.2. Каждая праволинейная грамматика эквивалентна некоторой праволинейной грамматике в нормальной форме.
Доказательство. Применим последовательно теорему 2.4.3, лемму 2.3.3 и воспользуемся конструкцией из доказательства теоремы 2.4.1.
Теорема 2.5.3. Если праволинейный язык не содержит пустого слова, то он порождается некоторой праволинейной грамматикой в нормальной форме без -правил.
Детерминированные конечные автоматы
Определение 2.6.1. Конечный автомат называется детерминированным (deterministic), если
1. множество I содержит ровно один элемент;
2. для каждого перехода выполняется равенство |x| = 1;
3. для любого символа и для любого состояния существует не более одного состояния со свойством .
Пример 2.6.2. Конечный автомат из примера 2.1.14 является детерминированным.
|
|
Определение 2.6.3. Детерминированный конечный автомат называется полным (complete), если для каждого состояния и для каждого символа найдется такое состояние , что .
Пример 2.6.4. Конечный автомат из примера 2.1.14 эквивалентен полному детерминированному конечному автомату , где Q = {1,2,3}, , I = {1}, F = {1,2},
Замечание 2.6.5. Некоторые авторы используют в определении полного детерминированного конечного автомата вместо отношения функцию . От функции можно перейти к отношению , положив