4624
правки
KEV (обсуждение | вклад) (Создана новая страница размером '''Формальный язык''' (''Formal language'') - произвольное множество <math>L</math>...) |
KEV (обсуждение | вклад) Нет описания правки |
||
Строка 10: | Строка 10: | ||
определяется по следующим правилам: | определяется по следующим правилам: | ||
(1) <math> L^o = \{e\}</math> | |||
(2) <math> L^n = LL^{n-1} \mbox{ для } n \geq 1</math> ; | |||
(3) <math> L^* = \bigcup\limits_{n\geq O} L^n </math> . | |||
''Позитивная итерация'' языка <math>L</math>, обозначаемая через | ''Позитивная итерация'' языка <math>L</math>, обозначаемая через | ||
Строка 20: | Строка 20: | ||
<math>L^+=LL^*=L^*L</math> и <math>L^*=L^+\cup\{e\}.</math> | <math>L^+=LL^*=L^*L</math> и <math>L^*=L^+\cup\{e\}.</math> | ||
Если язык <math>L</math> состоит из небольшого числа | Если язык <math>L</math> состоит из небольшого числа цепочек, то самый очевидный способ описания языка --- составить список всех цепочек из <math>L</math>. Однако многие языки (например, языки программирования) невозможно или нежелательно задавать исчерпывающим перечислением входящих в них цепочек, и поэтому, как правило, используются другие способы определения языка. Причем используются только такие способы, которые позволяют описанию языка быть обозримым (заведомо конечным), хотя описываемый язык может быть и бесконечным. Известно несколько методов определения языка, удовлетворяющих этому требованию. | ||
цепочек, то самый очевидный способ описания языка --- | |||
составить список всех цепочек из <math>L</math>. | |||
Однако многие языки (например, языки программирования) | |||
невозможно или нежелательно задавать исчерпывающим | |||
перечислением входящих в них цепочек, и поэтому, как | |||
правило, используются другие способы определения языка. | |||
Причем используются только такие способы, которые позволяют | |||
описанию языка быть обозримым (заведомо конечным), хотя | |||
описываемый язык может быть и бесконечным. Известно | |||
несколько методов определения языка, удовлетворяющих этому | |||
требованию. | |||
Один из них связан со способом задания множества с помощью | Один из них связан со способом задания множества с помощью характеристического свойства (предиката) и состоит в использовании частичного [[алгоритм|''алгоритма'']] (предписания производить некоторые действия), который для произвольной входной цепочки остановится и ответит "да" после конечного числа шагов, если эта цепочка принадлежит языку. Схематизированные устройства, используемые для представления таких алгоритмов, получили название [[распознаватель|''распознавателей'']]. Примерами распознавателей являются [[конечный автомат|''конечные автоматы'']], [[автомат с магазинной памятью|''автоматы с магазинной памятью'']] и [[машина Тьюринга|''машины Тьюринга'']]. | ||
характеристического свойства (предиката) и состоит в | |||
использовании частичного ''алгоритма'' (предписания производить | |||
некоторые действия), который для произвольной входной | |||
цепочки остановится и ответит "да" после конечного числа | |||
шагов, если эта цепочка принадлежит языку. | |||
Схематизированные устройства, используемые для представления | |||
таких алгоритмов, получили название ''распознавателей''. | |||
Примерами распознавателей являются | |||
''конечные автоматы'', ''автоматы с магазинной памятью'' и | |||
''машины Тьюринга''. | |||
Второй метод описания языка имеет вид исчисления, называемого [[грамматика|''грамматикой'']], --- некоторой порождающей системы (разрешения производить некоторые действия), используя которую можно получить (породить) все [[цепочка|цепочки]] языка <math>L</math> и только их. Одно из преимуществ определения языка с помощью грамматики состоит в том, что грамматика придает цепочкам ("предложениям") языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка. | Второй метод описания языка имеет вид исчисления, называемого [[грамматика|''грамматикой'']], --- некоторой порождающей системы (разрешения производить некоторые действия), используя которую можно получить (породить) все [[цепочка|цепочки]] языка <math>L</math> и только их. Одно из преимуществ определения языка с помощью грамматики состоит в том, что грамматика придает цепочкам ("предложениям") языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка. |