Формальный язык
Поделись знанием:
– Нет, господа, нет… вы не думайте… я очень понимаю, вы напрасно обо мне думаете так… я… для меня… я за честь полка.да что? это на деле я покажу, и для меня честь знамени…ну, всё равно, правда, я виноват!.. – Слезы стояли у него в глазах. – Я виноват, кругом виноват!… Ну, что вам еще?…
– Вот это так, граф, – поворачиваясь, крикнул штаб ротмистр, ударяя его большою рукою по плечу.
– Я тебе говог'ю, – закричал Денисов, – он малый славный.
– Так то лучше, граф, – повторил штаб ротмистр, как будто за его признание начиная величать его титулом. – Подите и извинитесь, ваше сиятельство, да с.
– Господа, всё сделаю, никто от меня слова не услышит, – умоляющим голосом проговорил Ростов, – но извиняться не могу, ей Богу, не могу, как хотите! Как я буду извиняться, точно маленький, прощенья просить?
Денисов засмеялся.
– Вам же хуже. Богданыч злопамятен, поплатитесь за упрямство, – сказал Кирстен.
– Ей Богу, не упрямство! Я не могу вам описать, какое чувство, не могу…
– Ну, ваша воля, – сказал штаб ротмистр. – Что ж, мерзавец то этот куда делся? – спросил он у Денисова.
– Сказался больным, завтг'а велено пг'иказом исключить, – проговорил Денисов.
– Это болезнь, иначе нельзя объяснить, – сказал штаб ротмистр.
– Уж там болезнь не болезнь, а не попадайся он мне на глаза – убью! – кровожадно прокричал Денисов.
В комнату вошел Жерков.
– Ты как? – обратились вдруг офицеры к вошедшему.
– Поход, господа. Мак в плен сдался и с армией, совсем.
– Врешь!
– Сам видел.
– Как? Мака живого видел? с руками, с ногами?
– Поход! Поход! Дать ему бутылку за такую новость. Ты как же сюда попал?
– Опять в полк выслали, за чорта, за Мака. Австрийской генерал пожаловался. Я его поздравил с приездом Мака…Ты что, Ростов, точно из бани?
– Тут, брат, у нас, такая каша второй день.
Вошел полковой адъютант и подтвердил известие, привезенное Жерковым. На завтра велено было выступать.
– Поход, господа!
– Ну, и слава Богу, засиделись.
Кутузов отступил к Вене, уничтожая за собой мосты на реках Инне (в Браунау) и Трауне (в Линце). 23 го октября .русские войска переходили реку Энс. Русские обозы, артиллерия и колонны войск в середине дня тянулись через город Энс, по сю и по ту сторону моста.
День был теплый, осенний и дождливый. Пространная перспектива, раскрывавшаяся с возвышения, где стояли русские батареи, защищавшие мост, то вдруг затягивалась кисейным занавесом косого дождя, то вдруг расширялась, и при свете солнца далеко и ясно становились видны предметы, точно покрытые лаком. Виднелся городок под ногами с своими белыми домами и красными крышами, собором и мостом, по обеим сторонам которого, толпясь, лилися массы русских войск. Виднелись на повороте Дуная суда, и остров, и замок с парком, окруженный водами впадения Энса в Дунай, виднелся левый скалистый и покрытый сосновым лесом берег Дуная с таинственною далью зеленых вершин и голубеющими ущельями. Виднелись башни монастыря, выдававшегося из за соснового, казавшегося нетронутым, дикого леса; далеко впереди на горе, по ту сторону Энса, виднелись разъезды неприятеля.
Между орудиями, на высоте, стояли спереди начальник ариергарда генерал с свитским офицером, рассматривая в трубу местность. Несколько позади сидел на хоботе орудия Несвицкий, посланный от главнокомандующего к ариергарду.
Казак, сопутствовавший Несвицкому, подал сумочку и фляжку, и Несвицкий угощал офицеров пирожками и настоящим доппелькюмелем. Офицеры радостно окружали его, кто на коленах, кто сидя по турецки на мокрой траве.
– Да, не дурак был этот австрийский князь, что тут замок выстроил. Славное место. Что же вы не едите, господа? – говорил Несвицкий.
– Покорно благодарю, князь, – отвечал один из офицеров, с удовольствием разговаривая с таким важным штабным чиновником. – Прекрасное место. Мы мимо самого парка проходили, двух оленей видели, и дом какой чудесный!
– Посмотрите, князь, – сказал другой, которому очень хотелось взять еще пирожок, но совестно было, и который поэтому притворялся, что он оглядывает местность, – посмотрите ка, уж забрались туда наши пехотные. Вон там, на лужку, за деревней, трое тащут что то. .Они проберут этот дворец, – сказал он с видимым одобрением.
– И то, и то, – сказал Несвицкий. – Нет, а чего бы я желал, – прибавил он, прожевывая пирожок в своем красивом влажном рте, – так это вон туда забраться.
(перенаправлено с «Формализованный язык»)
Не следует путать с формальным стилем речи.
Формальный язык в математической логике и информатике — множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.
В теории моделей язык строится из множеств символов, функций и отношений вместе с их арностью, а также множества переменных. Каждое из этих множеств может быть бесконечным. Из языка вместе с универсальными логическими символами составляются логические высказывания.
Содержание
Определение
Формальный язык может быть определён по-разному, например:
- Простым перечислением слов, входящих в данный язык. Этот способ, в основном, применим для определения конечных языков и языков простой структуры.
- Словами, порождёнными некоторой формальной грамматикой (см. иерархия Хомского).
- Словами, порождёнными регулярным выражением.
- Словами, распознаваемыми некоторым конечным автоматом.
- Словами, порождёнными БНФ-конструкцией.
Например, если алфавит задан как <math>\{a, b\}</math>, а язык <math>L</math> включает в себя все слова над ним, то слово <math>ababba</math> принадлежит <math>L</math>. Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как <math>e</math>, <math>\epsilon</math> или <math>\Lambda</math>.
Некоторые другие примеры формальных языков:
- множество <math>\{ a^n\}</math>, где <math>n</math> — неотрицательное число, а <math>a^{n}</math> означает, что <math>a</math> повторяется <math>n</math> раз;
- множество синтаксически корректных программ в данном языке программирования.
Операции
Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что <math>L_{1}</math> и <math>L_{2}</math> являются языками, определёнными над некоторым общим алфавитом.
- Конкатенация (сцепление) <math>L_{1}L_{2}</math> содержит все слова, удовлетворяющие форме <math>vw</math>, где <math>v</math> — это слово из <math>L_{1}</math>, а <math>w</math> — слово из <math>L_{2}</math>.
- Пересечение <math>L_1 \cap L_2</math> содержит все слова, содержащиеся и в <math>L_1</math>, и в <math>L_{2}</math>.
- Объединение <math>L_1 \cup L_2</math> содержит все слова, содержащиеся или в <math>L_{1}</math>, или в <math>L_{2}</math>.
- Дополнение языка <math>L_{1}</math> содержит все слова алфавита, которые не содержатся в <math>L_{1}</math>.
- Правое отношение <math>L_{1}/L_{2}</math> содержит все слова <math>v</math>, для которых существует слово <math>w</math> в <math>L_{2}</math> такое, что <math>vw</math> находилось в <math>L_{1}</math>.
- Замыкание Клини <math>L_{1}^{*}</math> содержит все слова, которые могут быть записаны в форме <math>w_{1}w_{2}...w_{n}</math>, где <math>w_{i}</math> содержится в <math>L_{1}</math> и <math>n \ge 0</math>. Следует помнить, что это включает и пустое слово <math>\epsilon</math>, так как <math>n = 0</math> допустимо по условию.
- Обращение <math>L_{1}^{R}</math> содержит обращённые слова из <math>L_{1}</math>.
- Смешение <math>L_{1}</math> и <math>L_{2}</math> содержит все слова, которые могут быть записаны в форме <math>v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}</math>, где <math>n \ge 1</math> и <math>v_{1},...,v_{n}</math> являются такими словами, что связь <math>v_{1}...v_{n}</math> находится в <math>L_{1}</math>, а <math>w_{1},...,w_{n}</math> являются такими словами, что <math>w_{1}...w_{n}</math> находятся в <math>L_{2}</math>.
См. также
Напишите отзыв о статье "Формальный язык"
Литература
- Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973. — 368 с.
- Хопкрофт, Дж., Мотвани, Р., Дж. Ульман. Введение в теорию автоматов, языков и вычислений. — М.: Вильямс, 2002 (пер. издания Addison Wesley). — 528 с. — ISBN 5-8459-0261-4
- Кревский И. Г., Селивёрстов М. Н., Григорьева К. В. Формальные языки, грамматики и основы построения трансляторов: Учебное пособие / Под ред. А. М. Бершадского. — Пенза: Изд-во Пенз. гос. ун-та, 2002. — 124 с.
- Мартыненко Б. К. Языки и трансляции: Учебное пособие. — СПб.: Издательство С.-Петербургского университета, 2003. — 235 с.
- Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. [trpl7.ru/t-books/TRYAP_BOOK_Details.htm Теория и реализация языков программирования] — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
- Пентус А. Е., Пентус М. Р. Математическая теория формальных языков. — М.: Интернет-университет информационных технологий, Бином. Лаборатория знаний, 2006. — 248 с.
- Фомичёв В. С. [old.eltech.ru/misc/LGA_2007_FINAL/Index.html Формальные языки, грамматики и автоматы: Курс лекций] — Интернет-публикация, 2006.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Формальный язык
Ростов, краснея и бледнея, смотрел то на одного, то на другого офицера.– Нет, господа, нет… вы не думайте… я очень понимаю, вы напрасно обо мне думаете так… я… для меня… я за честь полка.да что? это на деле я покажу, и для меня честь знамени…ну, всё равно, правда, я виноват!.. – Слезы стояли у него в глазах. – Я виноват, кругом виноват!… Ну, что вам еще?…
– Вот это так, граф, – поворачиваясь, крикнул штаб ротмистр, ударяя его большою рукою по плечу.
– Я тебе говог'ю, – закричал Денисов, – он малый славный.
– Так то лучше, граф, – повторил штаб ротмистр, как будто за его признание начиная величать его титулом. – Подите и извинитесь, ваше сиятельство, да с.
– Господа, всё сделаю, никто от меня слова не услышит, – умоляющим голосом проговорил Ростов, – но извиняться не могу, ей Богу, не могу, как хотите! Как я буду извиняться, точно маленький, прощенья просить?
Денисов засмеялся.
– Вам же хуже. Богданыч злопамятен, поплатитесь за упрямство, – сказал Кирстен.
– Ей Богу, не упрямство! Я не могу вам описать, какое чувство, не могу…
– Ну, ваша воля, – сказал штаб ротмистр. – Что ж, мерзавец то этот куда делся? – спросил он у Денисова.
– Сказался больным, завтг'а велено пг'иказом исключить, – проговорил Денисов.
– Это болезнь, иначе нельзя объяснить, – сказал штаб ротмистр.
– Уж там болезнь не болезнь, а не попадайся он мне на глаза – убью! – кровожадно прокричал Денисов.
В комнату вошел Жерков.
– Ты как? – обратились вдруг офицеры к вошедшему.
– Поход, господа. Мак в плен сдался и с армией, совсем.
– Врешь!
– Сам видел.
– Как? Мака живого видел? с руками, с ногами?
– Поход! Поход! Дать ему бутылку за такую новость. Ты как же сюда попал?
– Опять в полк выслали, за чорта, за Мака. Австрийской генерал пожаловался. Я его поздравил с приездом Мака…Ты что, Ростов, точно из бани?
– Тут, брат, у нас, такая каша второй день.
Вошел полковой адъютант и подтвердил известие, привезенное Жерковым. На завтра велено было выступать.
– Поход, господа!
– Ну, и слава Богу, засиделись.
Кутузов отступил к Вене, уничтожая за собой мосты на реках Инне (в Браунау) и Трауне (в Линце). 23 го октября .русские войска переходили реку Энс. Русские обозы, артиллерия и колонны войск в середине дня тянулись через город Энс, по сю и по ту сторону моста.
День был теплый, осенний и дождливый. Пространная перспектива, раскрывавшаяся с возвышения, где стояли русские батареи, защищавшие мост, то вдруг затягивалась кисейным занавесом косого дождя, то вдруг расширялась, и при свете солнца далеко и ясно становились видны предметы, точно покрытые лаком. Виднелся городок под ногами с своими белыми домами и красными крышами, собором и мостом, по обеим сторонам которого, толпясь, лилися массы русских войск. Виднелись на повороте Дуная суда, и остров, и замок с парком, окруженный водами впадения Энса в Дунай, виднелся левый скалистый и покрытый сосновым лесом берег Дуная с таинственною далью зеленых вершин и голубеющими ущельями. Виднелись башни монастыря, выдававшегося из за соснового, казавшегося нетронутым, дикого леса; далеко впереди на горе, по ту сторону Энса, виднелись разъезды неприятеля.
Между орудиями, на высоте, стояли спереди начальник ариергарда генерал с свитским офицером, рассматривая в трубу местность. Несколько позади сидел на хоботе орудия Несвицкий, посланный от главнокомандующего к ариергарду.
Казак, сопутствовавший Несвицкому, подал сумочку и фляжку, и Несвицкий угощал офицеров пирожками и настоящим доппелькюмелем. Офицеры радостно окружали его, кто на коленах, кто сидя по турецки на мокрой траве.
– Да, не дурак был этот австрийский князь, что тут замок выстроил. Славное место. Что же вы не едите, господа? – говорил Несвицкий.
– Покорно благодарю, князь, – отвечал один из офицеров, с удовольствием разговаривая с таким важным штабным чиновником. – Прекрасное место. Мы мимо самого парка проходили, двух оленей видели, и дом какой чудесный!
– Посмотрите, князь, – сказал другой, которому очень хотелось взять еще пирожок, но совестно было, и который поэтому притворялся, что он оглядывает местность, – посмотрите ка, уж забрались туда наши пехотные. Вон там, на лужку, за деревней, трое тащут что то. .Они проберут этот дворец, – сказал он с видимым одобрением.
– И то, и то, – сказал Несвицкий. – Нет, а чего бы я желал, – прибавил он, прожевывая пирожок в своем красивом влажном рте, – так это вон туда забраться.
