Регулярная грамматика: различия между версиями
Перейти к навигации
Перейти к поиску
KVN (обсуждение | вклад) (Создана новая страница размером Праволинейная грамматика <math>G=(N,\Sigma,P,S)</math> называется ''регулярной'' (или [[...) |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
[[Праволинейная грамматика]] | [[Праволинейная грамматика]] <math>G=(N,\Sigma,P,S)</math> называется ''регулярной'' (или [[Автоматная грамматика|''автоматной'']]), если | ||
<math>G=(N,\Sigma,P,S)</math> называется ''регулярной'' (или [[Автоматная грамматика|''автоматной'']]), если | |||
(1) все ее правила, за исключением <math>S \longrightarrow e</math>, имеют | (1) все ее правила, за исключением <math>S \longrightarrow e</math>, имеют | ||
вид <math>A\longrightarrow aB</math> или <math>A\longrightarrow a</math>, где <math>B\in N</math>, <math>a\in\Sigma</math>, | вид <math>A\longrightarrow aB</math> или <math>A\longrightarrow a</math>, где <math>B\in N</math>, <math>a\in\Sigma</math>, | ||
(2) если <math>S\longrightarrow e</math> принадлежит <math>P</math>, то <math>S</math> не | (2) если <math>S\longrightarrow e</math> принадлежит <math>P</math>, то <math>S</math> не встречается в правых частях правил. | ||
встречается в правых частях правил. | |||
==Литература== | ==Литература== | ||
*Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
*Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
*Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: НГУ, 2018. | |||
*Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
[ | [[Категория: Теория формальных языков]] | ||
[[Категория:Синтаксические деревья]] | |||
[ | |||
[[Категория: | |||
Текущая версия от 11:19, 5 ноября 2024
Праволинейная грамматика [math]\displaystyle{ G=(N,\Sigma,P,S) }[/math] называется регулярной (или автоматной), если
(1) все ее правила, за исключением [math]\displaystyle{ S \longrightarrow e }[/math], имеют вид [math]\displaystyle{ A\longrightarrow aB }[/math] или [math]\displaystyle{ A\longrightarrow a }[/math], где [math]\displaystyle{ B\in N }[/math], [math]\displaystyle{ a\in\Sigma }[/math],
(2) если [math]\displaystyle{ S\longrightarrow e }[/math] принадлежит [math]\displaystyle{ P }[/math], то [math]\displaystyle{ S }[/math] не встречается в правых частях правил.
Литература
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
- Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: НГУ, 2018.
- Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.