1294
правки
Формальный язык: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 7: | Строка 7: | ||
<math>\{\alpha\beta: \alpha \in L_1 </math> и <math> \beta \in L_2\}.</math> | <math>\{\alpha\beta: \alpha \in L_1 </math> и <math> \beta \in L_2\}.</math> | ||
''Итерация'' языка <math>L</math>, обозначаемая через <math>L^*</math>, | [[Итерация|''Итерация'']] языка <math>L</math>, обозначаемая через <math>L^*</math>, | ||
определяется по следующим правилам: | определяется по следующим правилам: | ||
| Строка 16: | Строка 16: | ||
(3) <math> L^* = \bigcup\limits_{n\geq O} L^n </math> . | (3) <math> L^* = \bigcup\limits_{n\geq O} L^n </math> . | ||
''Позитивная итерация'' языка <math>L</math>, обозначаемая через | [[Позитивная итерация|''Позитивная итерация'']] языка <math>L</math>, обозначаемая через | ||
<math>L^+</math> , --- это язык <math>\bigcup\limits_{n\geq 1} L^n</math>. Заметим, что | <math>L^+</math> , --- это язык <math>\bigcup\limits_{n\geq 1} L^n</math>. Заметим, что | ||
<math>L^+=LL^*=L^*L</math> и <math>L^*=L^+\cup\{e\}.</math> | <math>L^+=LL^*=L^*L</math> и <math>L^*=L^+\cup\{e\}.</math> | ||
| Строка 26: | Строка 26: | ||
Второй метод описания языка имеет вид исчисления, называемого [[грамматика|''грамматикой'']], --- некоторой порождающей системы (разрешения производить некоторые действия), используя которую можно получить (породить) все [[цепочка|цепочки]] языка <math>L</math> и только их. Одно из преимуществ определения языка с помощью грамматики состоит в том, что грамматика придает цепочкам ("предложениям") языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка. | Второй метод описания языка имеет вид исчисления, называемого [[грамматика|''грамматикой'']], --- некоторой порождающей системы (разрешения производить некоторые действия), используя которую можно получить (породить) все [[цепочка|цепочки]] языка <math>L</math> и только их. Одно из преимуществ определения языка с помощью грамматики состоит в том, что грамматика придает цепочкам ("предложениям") языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка. | ||
Язык <math>L</math> называется ''автоматным, праволинейным, регулярным, контекстно-свободным, контекстно-зависимым'' и т.д., если существует ''грамматика'' <math>G</math> соответствующего типа, которая порождает этот язык, т.е. для которой <math>L(G)=L</math>. | Язык <math>L</math> называется [[Автоматный язык|''автоматным'']], [[Праволинейный язык|''праволинейным'']], [[Регулярный язык|''регулярным'']], [[Контекстно-свободный язык|''контекстно-свободным'']], [[Контекстно-зависимый язык|''контекстно-зависимым'']] и т.д., если существует [[Грамматика|''грамматика'']] <math>G</math> соответствующего типа, которая порождает этот язык, т.е. для которой <math>L(G)=L</math>. | ||
==Литература== | ==Литература== | ||