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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
'''Формальный язык''' ([[Formal language|''Formal language'']]) - произвольное множество <math>L</math> цепочек в некотором заданном алфавите <math>\Sigma</math>, т.е. <math>L \subseteq \Sigma^*</math>.
'''Формальный язык''' (''[[Formal language]]'') произвольное множество <math>\,L</math> цепочек в некотором заданном алфавите <math>\,\Sigma,</math> т.е. <math>L \subseteq \Sigma^*</math>.


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


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


[[Итерация|''Итерация'']] языка <math>L</math>, обозначаемая через <math>L^*</math>,
:::::<math>\{\alpha\beta: \alpha \in L_1 </math> и <math> \beta \in L_2\}.</math>
 
''[[Итерация языка]]'' <math>\,L,</math> обозначаемая через <math>\,L^*,</math>
определяется по следующим правилам:
определяется по следующим правилам:


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


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


(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^+=LL^*=L^*L</math> и <math>\,L^*=L^+\cup\{e\}.</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</math> состоит из небольшого числа цепочек, то самый очевидный способ описания языка --- составить список всех цепочек из <math>L</math>. Однако многие языки (например, языки программирования) невозможно или нежелательно задавать исчерпывающим перечислением входящих в них цепочек, и поэтому, как правило, используются другие способы определения языка. Причем используются только такие способы, которые позволяют описанию языка быть обозримым (заведомо конечным), хотя описываемый язык может быть и бесконечным. Известно несколько методов определения языка, удовлетворяющих этому требованию.
Если язык <math>\,L</math> состоит из небольшого числа цепочек, то самый очевидный способ описания языка составить список всех цепочек из <math>\,L.</math> Однако многие языки (например, языки программирования) невозможно или нежелательно задавать исчерпывающим перечислением входящих в них цепочек, и поэтому, как правило, используются другие способы определения языка. Причем используются только такие способы, которые позволяют описанию языка быть обозримым (заведомо конечным), хотя описываемый язык может быть и бесконечным. Известно несколько методов определения языка, удовлетворяющих этому требованию.


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


Второй метод описания языка имеет вид исчисления, называемого [[грамматика|''грамматикой'']], --- некоторой порождающей системы (разрешения производить некоторые действия), используя которую можно получить (породить) все [[цепочка|цепочки]] языка <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>.


==Литература==
==Литература==
[Ахо-Ульман],
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
 
* Бауэр Ф.Л., Гооз Г. Информатика. — М: Мир, 1990. — Т. 1,2.


[Бауэр-Гооз],  
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.


[Касьянов/95],
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.


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




[[Категория: Теория формальных языков]].
[[Категория: Теория формальных языков]].

Текущая версия от 12:06, 29 сентября 2011

Формальный язык (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 }[/math] и [math]\displaystyle{ \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} }[/math] для [math]\displaystyle{ 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].

Литература

  • Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
  • Бауэр Ф.Л., Гооз Г. Информатика. — М: Мир, 1990. — Т. 1,2.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
  • Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986..