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

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

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