| Автомат
| Грамматика
|
  алфавит  состояние- функция перехода
- начальное состояние
- конечные состояния
| - алфавит
- правила
|
Регулярная цепочка – цепочка, составленная по правилам грамматики
Регулярная цепочка – цепочка, которая может быть распознана распознающим автоматом
ε – пустая цепочка (всегда регулярная)
По заданным правилам переходов составляем таблицу переходов.
Если две регулярные цепочки abcb и bcac допустимы, то
- abcbbcac – цепочка, образованная при конкатенации этих двух является регулярным выражением.
- abcbabcb – итерация одной регулярной цепочки
- замыкание Клини (Kleene) –
- Объединение – объединение регулярных цепочек разных языков (L, S), обработанных разными автоматами (L U S)
