Формальный язык

Структура синтаксически правильно сформированного, хотя и бессмысленного, английского предложения «Бесцветные зеленые идеи яростно спят» ( исторический пример из Хомского 1957 г.).

В математике , информатике и лингвистике , формальный язык состоит из слов , чьи буквы взяты из алфавита и хорошо сформированы в соответствии с определенным набором правил.

Алфавит формального языка состоит из символов, букв, или маркеров , которые СЦЕПЯТ в строки языка. ^[1] Каждая строка, составленная из символов этого алфавита, называется словом, а слова, принадлежащие определенному формальному языку, иногда называются правильно сформированными словами или правильно сформированными формулами . Формальный язык часто определяется с помощью формальной грамматики, такой как обычная грамматика или контекстно-свободная грамматика , которая состоит из правил ее формирования .

Теория формального языка изучает в первую очередь чисто синтаксические аспекты таких языков, то есть их внутренние структурные паттерны. Теория формального языка возникла из лингвистики как способ понимания синтаксических закономерностей естественных языков . В информатике формальные языки используются, среди прочего, в качестве основы для определения грамматики языков программирования и формализованных версий подмножеств естественных языков, в которых слова языка представляют концепции, связанные с определенными значениями или семантикой . В теории вычислительной сложности , проблемы , решенияобычно определяются как формальные языки, а классы сложности определяются как наборы формальных языков, которые могут быть проанализированы машинами с ограниченной вычислительной мощностью. В логике и в основах математики формальные языки используются для представления синтаксиса аксиоматических систем , а математический формализм - это философия, согласно которой вся математика может быть сведена таким образом к синтаксическому манипулированию формальными языками.

История [ править ]

Первым формальным языком считается тот, который использовал Готтлоб Фреге в его Begriffsschrift (1879), буквально означающий «написание концептов», и который Фреге описал как «формальный язык чистой мысли». ^[2]

Ранняя система полутхуэ Акселя Туе , которую можно использовать для переписывания строк, оказала влияние на формальную грамматику .

Слова над алфавитом [ править ]

Алфавит , в контексте формальных языков, может быть любым набором , хотя часто имеет смысл использовать алфавит в обычном смысле этого слова, или в более общем случае набор символов , такие как ASCII или Unicode . Элементы алфавита называются его буквами . Алфавит может содержать бесконечное количество элементов; ^{[примечание 1],} однако, большинство определений в теории формального языка определяют алфавиты с конечным числом элементов, и большинство результатов применимо только к ним.

Слово в алфавите может быть любой конечной последовательности (то есть, строка ) букв. Множество всех слов в алфавите Σ обычно обозначается Σ ^* ( звездой Клини ). Длина слова - это количество букв, из которых оно состоит. Для любого алфавита существует только одно слово длины 0, пустое слово , которое часто обозначается буквами e, ε, λ или даже Λ. Путем конкатенации можно объединить два слова, чтобы сформировать новое слово, длина которого равна сумме длин исходных слов. Результатом соединения слова с пустым словом является исходное слово.

В некоторых приложениях, особенно в логике , алфавит также известен как словарь, а слова - как формулы или предложения ; это разрушает метафору буквы / слова и заменяет ее метафорой слова / предложения.

Определение [ править ]

Формальный язык L над алфавитом Е является подмножеством из Е ^* , то есть, набор слов над этой азбукой. Иногда наборы слов группируются в выражения, тогда как правила и ограничения могут быть сформулированы для создания «правильно сформированных выражений».

В информатике и математике, которые обычно не имеют дело с естественными языками , прилагательное «формальный» часто опускается как избыточное.

В то время как формальная теория языка обычно занимается формальными языками, которые описываются некоторыми синтаксическими правилами, фактическое определение понятия «формальный язык» такое же, как указано выше: (возможно, бесконечный) набор строк конечной длины, составленных из заданного алфавита, не больше и не меньше. На практике существует множество языков, которые можно описать правилами, например, обычные языки или контекстно-свободные языки . Понятие формальной грамматики может быть ближе к интуитивному понятию «языка», описываемому синтаксическими правилами. Из-за злоупотребления определением конкретный формальный язык часто считается оснащенным формальной грамматикой, описывающей его.

Примеры [ править ]

Следующие правила описывают формальный язык  L над алфавитом Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:

• Каждая непустая строка , которая не содержит «+» или «=» и не начинается с «0» в  L .
• Строка «0» в  L .
• Строка , содержащая «=» в  L тогда и только тогда , когда имеется ровно один «=», и она разделяет две действительные строки  L .
• Строка , содержащая «+» , но не «=» в  L тогда и только тогда , когда каждый «+» в строке разделяет две действительные строки  L .
• В L нет строк,  кроме тех, которые подразумеваются предыдущими правилами.

Согласно этим правилам, строка «23 + 4 = 555» находится в  L , а строка «= 234 = +» - нет. Этот формальный язык выражает натуральные числа , правильно сформированные сложения и правильно сформированные равенства сложения, но он выражает только то, как они выглядят (их синтаксис ), а не то, что они означают ( семантика ). Например, нигде в этих правилах нет указания, что «0» означает число ноль, «+» означает сложение, «23 + 4 = 555» неверно и т. Д.

Конструкции [ править ]

Для конечных языков можно явно перечислить все правильно сформированные слова. Например, мы можем описать язык  L как L  = {a, b, ab, cba}. Вырожденный случай этой конструкции является пустым языком , который не содержит ни одного слова на всех ( L  =  ∅ ).

Однако даже в конечном (непустом) алфавите, таком как Σ = {a, b}, существует бесконечное количество слов конечной длины, которые потенциально могут быть выражены: «a», «abb», «ababba», » aaababbbbaab ", .... Следовательно, формальные языки обычно бесконечны, и описать бесконечный формальный язык не так просто, как написать L  = {a, b, ab, cba}. Вот несколько примеров формальных языков:

• L = Σ ^* , множество всех слов над Σ;
• L = {a} ^* = {a ⁿ }, где n пробегает натуральные числа, а «a ⁿ » означает «a», повторяющееся n раз (это набор слов, состоящий только из символа «a»);
• набор синтаксически корректных программ на данном языке программирования (синтаксис которых обычно определяется контекстно-свободной грамматикой );
• набор входных данных, на которых останавливается определенная машина Тьюринга ; или же
• набор максимальных строк буквенно-цифровых символов ASCII в этой строке, т. е.
  набор {the, set, of, maximal, strings, alphanumeric, ASCII, characters, on, this, line, i, e}.

Формализмы спецификации языка [ править ]

Формальные языки используются в качестве инструментов во многих дисциплинах. Однако формальная теория языка редко занимается конкретными языками (за исключением примеров), а в основном занимается изучением различных типов формализмов для описания языков. Например, язык может быть задан как

• те строки, которые генерируются формальной грамматикой ;
• те строки, которые описаны или соответствуют определенному регулярному выражению ;
• те строки, которые принимаются некоторым автоматом , таким как машина Тьюринга или конечный автомат ;
• те строки, для которых некоторая процедура принятия решения ( алгоритм, который задает последовательность связанных вопросов ДА / НЕТ) дает ответ ДА.

Типичные вопросы, которые задают о таких формализмах, включают:

• В чем их выразительная сила? (Может ли формализм X описать каждый язык, который может описать формализм Y ? Может ли он описывать другие языки?)
• В чем их узнаваемость? (Насколько сложно определить, принадлежит ли данное слово языку, описываемому формализмом X ?)
• В чем их сопоставимость? (Насколько сложно решить, являются ли два языка, один из которых описан в формализме X, а другой - в формализме Y , или снова в X , одним и тем же языком?).

Удивительно часто, но ответ на эти проблемы принятия решения - «это вообще невозможно сделать» или «это чрезвычайно дорого» (с указанием того, насколько дорого). Таким образом, формальная теория языка является одной из основных областей применения теории вычислимости и теории сложности . Формальные языки могут быть классифицированы в иерархии Хомского на основании выразительной силы их порождающей грамматики, а также сложности их распознающего автомата . Грамматики без контекста и обычные грамматики обеспечивают хороший компромисс между выразительностью и простотой синтаксического анализа и широко используются в практических приложениях.

Операции с языками [ править ]

Некоторые операции с языками являются общими. Сюда входят стандартные операции над множеством, такие как объединение, пересечение и дополнение. Другой класс операций - это поэлементное применение строковых операций.

Примеры: предположим, что и являются языками над некоторым общим алфавитом .${\ displaystyle L_ {1}}$${\ displaystyle L_ {2}}$${\ displaystyle \ Sigma}$

• Конкатенации состоит из всех строк в виде , где является строкой из и является строкой из .${\ Displaystyle L_ {1} \ cdot L_ {2}}$${\ displaystyle vw}$${\ displaystyle v}$${\ displaystyle L_ {1}}$${\ displaystyle w}$${\ displaystyle L_ {2}}$
• Пересечение из и состоит из всех строк, содержащихся в обоих языках${\ displaystyle L_ {1} \ cap L_ {2}}$${\ displaystyle L_ {1}}$${\ displaystyle L_ {2}}$
• Комплемент в отношении состоит из всех строк над , которые не являются в .${\ displaystyle \ neg L_ {1}}$${\ displaystyle L_ {1}}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle L_ {1}}$
• Клини звезда : язык , состоящий из всех слов, которые конкатенация или нескольких слов на языке оригинала;
• Реверс :
  • Тогда пусть ε - пустое слово и${\ Displaystyle \ varepsilon ^ {R} = \ varepsilon}$
  • для каждого непустого слова (где элементы некоторого алфавита) пусть ,${\displaystyle w=\sigma _{1}\cdots \sigma _{n}}$${\displaystyle \sigma _{1},\ldots ,\sigma _{n}}$${\displaystyle w^{R}=\sigma _{n}\cdots \sigma _{1}}$
  • то для формального языка , .${\displaystyle L}$${\displaystyle L^{R}=\{w^{R}\mid w\in L\}}$
• Гомоморфизм струн

Такие строковые операции используются для исследования закрывающих свойств классов языков. Класс языков закрывается при определенной операции, когда операция, примененная к языкам в классе, всегда снова создает язык в том же классе. Например, известно, что контекстно-свободные языки закрыты относительно объединения, конкатенации и пересечения с регулярными языками , но не замкнуты относительно пересечения или дополнения. Теория троек и абстрактных семейств языков изучает наиболее общие свойства замыкания языковых семейств сами по себе. ^[3]

Свойства замыкания языковых семей ( Op, где оба и находятся в языковой семье, указанной в столбце). После Хопкрофта и Ульмана.${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$

Операция		Обычный	DCFL	CFL	IND	CSL	рекурсивный	RE
Союз	${\displaystyle L_{1}\cup L_{2}=\{w\mid w\in L_{1}\lor w\in L_{2}\}}$	да	Нет	да	да	да	да	да
Пересечение	${\displaystyle L_{1}\cap L_{2}=\{w\mid w\in L_{1}\land w\in L_{2}\}}$	да	Нет	Нет	Нет	да	да	да
Дополнение	${\displaystyle \neg L_{1}=\{w\mid w\not \in L_{1}\}}$	да	да	Нет	Нет	да	да	Нет
Конкатенация	${\displaystyle L_{1}\cdot L_{2}=\{wz\mid w\in L_{1}\land z\in L_{2}\}}$	да	Нет	да	да	да	да	да
Клини звезда	${\displaystyle L_{1}^{*}=\{\varepsilon \}\cup \{wz\mid w\in L_{1}\land z\in L_{1}^{*}\}}$	да	Нет	да	да	да	да	да
(Строка) гомоморфизм ${\displaystyle h}$	${\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}$	да	Нет	да	да	Нет	Нет	да
ε-свободный (струнный) гомоморфизм ${\displaystyle h}$	${\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}$	да	Нет	да	да	да	да	да
Замена ${\displaystyle \varphi }$	${\displaystyle \varphi (L_{1})=\bigcup _{\sigma _{1}\cdots \sigma _{n}\in L_{1}}\varphi (\sigma _{1})\cdot \ldots \cdot \varphi (\sigma _{n})}$	да	Нет	да	да	да	Нет	да
Обратный гомоморфизм ${\displaystyle h^{-1}}$	${\displaystyle h^{-1}(L_{1})=\bigcup _{w\in L_{1}}h^{-1}(w)}$	да	да	да	да	да	да	да
Обеспечить регресс	${\displaystyle L^{R}=\{w^{R}\mid w\in L\}}$	да	Нет	да	да	да	да	да
Пересечение с обычным языком ${\displaystyle R}$	${\displaystyle L\cap R=\{w\mid w\in L\land w\in R\}}$	да	да	да	да	да	да	да

Приложения [ править ]

Языки программирования [ править ]

Компилятор обычно состоит из двух отдельных компонентов. Лексический анализатор , иногда генерируется с помощью инструмента , как lex, определяет знаки грамматики языка программирования, например , идентификаторы или ключевые слова , числовые и строковые литералы, знаки и символы операторов, которые сами определяются более простым формальным языком, как правило , с помощью регулярного выражения . На самом базовом концептуальном уровне синтаксический анализатор , иногда генерируемый генератором синтаксического анализатора, например yacc, пытается решить, является ли исходная программа синтаксически допустимой, то есть правильно ли она сформирована по отношению к грамматике языка программирования, для которой был построен компилятор.

Конечно, компиляторы делают больше, чем просто анализируют исходный код - они обычно переводят его в некоторый исполняемый формат. Из-за этого синтаксический анализатор обычно выводит больше, чем ответ да / нет, обычно абстрактное синтаксическое дерево . Это используется последующими этапами компилятора для создания исполняемого файла, содержащего машинный код, который запускается непосредственно на оборудовании, или некоторого промежуточного кода , для выполнения которого требуется виртуальная машина .

Формальные теории, системы и доказательства [ править ]

В математической логике , формальная теория представляет собой набор предложений , выраженные на формальном языке.

Формальная система (также называется логическое исчисление , или логическая система ) состоит из формального языка вместе с дедуктивным аппаратом (также называется дедуктивной системой ). Дедуктивный аппарат может состоять из набора правил преобразования , которые можно интерпретировать как действительные правила вывода, или набора аксиом , или иметь и то, и другое. Формальная система используется для получения одного выражения из одного или нескольких других выражений. Хотя формальный язык можно отождествить с его формулами, формальную систему нельзя отождествить с его теоремами. Две формальные системы и${\displaystyle {\mathcal {FS}}}$${\displaystyle {\mathcal {FS'}}}$ могут иметь все те же теоремы и при этом отличаться в некотором значительном теоретико-доказательственном отношении (формула A может быть синтаксическим следствием формулы B в одной, но не в другой, например).

Формальное доказательство или вывод является конечная последовательность правильно построенных формул (которые могут быть интерпретированы как предложения или предложений ) , каждая из которых является аксиомой или следует из предыдущих формул последовательности с помощью правила вывода . Последнее предложение в последовательности - это теорема формальной системы. Формальные доказательства полезны, потому что их теоремы можно интерпретировать как истинные утверждения.

Интерпретации и модели [ править ]

Формальные языки полностью синтаксичны по своей природе, но могут иметь семантику, которая придает значение элементам языка. Например, в математической логике набор возможных формул определенной логики является формальным языком, и интерпретация придает значение каждой из формул - обычно значение истинности .

Изучение интерпретаций формальных языков называется формальной семантикой . В математической логике это часто делается в терминах теории моделей . В теории моделей термины, встречающиеся в формуле, интерпретируются как объекты в математических структурах , а фиксированные правила композиционной интерпретации определяют, как значение истинности формулы может быть получено из интерпретации ее терминов; модель для формулы является интерпретацией таких терминов, что формула становится верной.

См. Также [ править ]

• Комбинаторика слов
• Бесплатный моноид
• Формальный метод
• Грамматическая структура
• Математические обозначения
• Ассоциативный массив
• Строка (информатика)

Примечания [ править ]

Ссылки [ править ]

Цитаты [ править ]

Источники [ править ]

Процитированные работы

Общие ссылки

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с формальными языками .

• "Формальный язык" , Энциклопедия математики , EMS Press , 2001 [1994]
• Университет Мэриленда , определения формального языка
• Джеймс Пауэр, «Заметки по теории и синтаксическому анализу формального языка» , 29 ноября 2002 г.
• Проекты некоторых глав "Handbook of Formal Language Theory", Vol. 1–3, Г. Розенберг и А. Саломаа (редакторы), Springer Verlag , (1997):
  • Александру Матееску и Арто Саломаа, «Предисловие» в томе 1, стр. V – viii, и «Формальные языки: введение и синопсис», глава 1 в томе. 1. С. 1-39.
  • Шэн Ю, «Обычные языки», глава 2 в томе. 1
  • Жан-Мишель Отбер, Жан Берстель, Люк Боассон, «Контекстно-свободные языки и автоматические выталкивающие элементы », Глава 3 в томе. 1
  • Кристиан Чоффрут и Юхани Кархумяки, «Комбинаторика слов», глава 6 в томе. 1
  • Теро Харью и Юхани Кархумяки, «Морфизмы», глава 7 в томе. 1. С. 439–510.
  • Жан-Эрик Пин, "Синтаксические полугруппы", глава 10 в томе. 1. С. 679–746.
  • М. Крочмор и К. Ханкарт, «Автоматы для сопоставления шаблонов», глава 9 в томе. 2
  • Дора Джаммаррези, Антонио Рестиво, «Двумерные языки», глава 4 в томе. 3. С. 215–267.