Формальный язык: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Формальный язык''' (''Formal language'') - произвольное множество <math>L</math>...)
 
Нет описания правки
Строка 10: Строка 10:
определяется по следующим правилам:
определяется по следующим правилам:


\smallskip(1) <math> L^o = \{e\}</math>
(1) <math> L^o = \{e\}</math>


\smallskip(2) <math> L^n = LL^{n-1} \mbox{ для } n \geq 1</math> ;
(2) <math> L^n = LL^{n-1} \mbox{ для } n \geq 1</math> ;


\smallskip(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>, обозначаемая через
Строка 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> и только их. Одно из преимуществ определения языка с помощью грамматики состоит в том, что грамматика придает цепочкам ("предложениям") языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка.

Версия от 16:35, 2 июня 2009

Формальный язык (Formal language) - произвольное множество [math]\displaystyle{ L }[/math] цепочек в некотором заданном алфавите [math]\displaystyle{ \Sigma }[/math], т.е. [math]\displaystyle{ L \subseteq \Sigma^* }[/math].

Так как язык --- это множество, то операции объединения,пересечения, нахождения разности и дополнения применимы и к языкам. Кроме того, различные операции, определенные для цепочек, применяются и к языкам (например, [math]\displaystyle{ L^R = \{\alpha^R : \alpha \in L\} }[/math]). Среди основных из них --- операции конкатенации и итерации.

Язык [math]\displaystyle{ L_1 L_2 }[/math], называемый конкатенацией (а также сцеплением или произведением) языков [math]\displaystyle{ L_1 }[/math] и [math]\displaystyle{ L_2 }[/math], --- это язык [math]\displaystyle{ \{\alpha\beta: \alpha \in L_1 \mbox{ и } \beta \in L_2\}. }[/math]

Итерация языка [math]\displaystyle{ L }[/math], обозначаемая через [math]\displaystyle{ L^* }[/math], определяется по следующим правилам:

(1) [math]\displaystyle{ L^o = \{e\} }[/math]

(2) [math]\displaystyle{ L^n = LL^{n-1} \mbox{ для } n \geq 1 }[/math] ;

(3) [math]\displaystyle{ L^* = \bigcup\limits_{n\geq O} L^n }[/math] .

Позитивная итерация языка [math]\displaystyle{ L }[/math], обозначаемая через [math]\displaystyle{ L^+ }[/math] , --- это язык [math]\displaystyle{ \bigcup\limits_{n\geq 1} L^n }[/math]. Заметим, что [math]\displaystyle{ L^+=LL^*=L^*L }[/math] и [math]\displaystyle{ L^*=L^+\cup\{e\}. }[/math]

Если язык [math]\displaystyle{ L }[/math] состоит из небольшого числа цепочек, то самый очевидный способ описания языка --- составить список всех цепочек из [math]\displaystyle{ L }[/math]. Однако многие языки (например, языки программирования) невозможно или нежелательно задавать исчерпывающим перечислением входящих в них цепочек, и поэтому, как правило, используются другие способы определения языка. Причем используются только такие способы, которые позволяют описанию языка быть обозримым (заведомо конечным), хотя описываемый язык может быть и бесконечным. Известно несколько методов определения языка, удовлетворяющих этому требованию.

Один из них связан со способом задания множества с помощью характеристического свойства (предиката) и состоит в использовании частичного алгоритма (предписания производить некоторые действия), который для произвольной входной цепочки остановится и ответит "да" после конечного числа шагов, если эта цепочка принадлежит языку. Схематизированные устройства, используемые для представления таких алгоритмов, получили название распознавателей. Примерами распознавателей являются конечные автоматы, автоматы с магазинной памятью и машины Тьюринга.

Второй метод описания языка имеет вид исчисления, называемого грамматикой, --- некоторой порождающей системы (разрешения производить некоторые действия), используя которую можно получить (породить) все цепочки языка [math]\displaystyle{ L }[/math] и только их. Одно из преимуществ определения языка с помощью грамматики состоит в том, что грамматика придает цепочкам ("предложениям") языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка.

Язык [math]\displaystyle{ L }[/math] называется автоматным, праволинейным, регулярным, контекстно-свободным, контекстно-зависимым и т.д., если существует грамматика [math]\displaystyle{ G }[/math] соответствующего типа, которая порождает этот язык, т.е. для которой [math]\displaystyle{ L(G)=L }[/math].

Литература

[Ахо-Ульман],

[Бауэр-Гооз],

[Касьянов/95],

[Касьянов-Поттосин]