Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 22 стр.

                                                                              22
        В алфавите А к регулярным выражениям относятся следующие:
1. Элемент А (или пустая строка).
Если P и Q – регулярные выражения, то регулярными будут также и
выражения
2. PQ (Q следует за P)
3. P | Q (P или Q)
4. P* (нуль или более экземпляров P)
        В алфавите {a, b, c}
ab* | ca* – регулярное выражение, которое описывает язык, включающий
следующие строки (помимо прочих):
abb c     caaa   ab    ca
        Пример        регулярного      выражения.        Регулярное   выражение,
описывающее идентификатор, имеет вид:
                 L ( L | D )*, где L обозначает букву, D – цифру.
        У регулярных выражений есть существенные ограничения. Например,
регулярное выражение не может задавать шаблоны скобок произвольной
длины, и, следовательно, их нельзя генерировать с помощью грамматики
типа 3.
        Пример нерегулярного выражения. Рассмотрим язык, состоящий из
строк открывающих и закрывающих скобок (плюс пустая строка),
обладающих следующими свойствами:
   1.) При чтении слева направо число встреченных закрывающих скобок
        никогда не превышает число встреченных открывающих скобок.
   2.) В каждой строке содержится одинаковое число открывающих и
        закрывающих скобок.
        Например, следующие строки принадлежат языку:
                      ()(()()(()))
                      (()()(()(())))(())
        а приводимые ниже – нет:
                      ( ( ( ) ( ) ) – не соответствует правилу 2.