Является ли язык описания регулярных выражений регулярным сам по себе?

Question

Если мы опишем регулярные выражения с операторами *, | и конкатенация . (который мы просто опускаем для ясности) и скобки (, ) и несколько букв из какого-то алфавита SigmaТогда язык, который описывает регулярные выражения, сам по себе регулярный? На мой взгляд, нет, потому что тот факт, что у нас есть скобки, означает, что никакой конечный автомат не может распознать ввод, поэтому это должен быть язык без контекста.

Примечание по не по теме

Я придерживаюсь своей позиции, что этот вопрос имеет отношение к программированию, так как я придумал его, думая о кодировании распознавателя регулярных выражений. Если кто-то захочет реализовать такую ​​вещь, то вскоре поймете, что вам действительно нужен не зависящий от контекста синтаксический анализатор для анализа регулярных выражений, и этот вопрос ответит на это. Более того, ответ и вопрос не являются "очень теоретическими", поскольку тема конечных автоматов считается материалом для студентов 1 и 2-го года обучения, поэтому внесение его в теоретический раздел информатики будет лишним.

Answer 1

Нет, это не регулярно. Учтите, что язык сбалансированных скобок даже не является регулярным. Противоречие с использованием леммы прокачки для языка сбалансированных скобок также работает для языка регулярных выражений.

Это не зависит от контекста, и его очень легко описать с помощью контекстно-свободной грамматики:

S -> SS
S -> S|S
S -> S*
S -> (S)
S -> a
S -> b
S -> c
S -> ...     // Continue for all terminals in the alphabet, and
S -> epsilon // The empty string