Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Автоматные языки и грамматики. Задача трансляции автоматных языков.




Грамматики типа 3 называют автоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид:

 

<A> a или <A> a<B> или <A> <B>a,

 

где a Vт, <A>, <B> VА, причем грамматика может иметь только правила вида <A> a<B> - правосторонние правила, либо только вида <A> <B>a - левосторонние правила. Примерами автоматных грамматик могут служить правосторонняя грамматика Г1. 6 и левосторонняя грамматика Г1. 7.

Г1. 6

Vт = {a, b}, VА = {<I>, <A>},

R = { <I> a<I>,

<I> a<A>,

<A> b<A>,

<A> b<Z>,

<Z> $ }

 

Г1. 7

Vт = {a, b}, VА = {<I>, <A>},

R = { <I> <A>b,

<A> <A>b,

<A> <Z>a,

<Z> <Z>a,

<Z> $ }

 

Эти грамматики являются эквивалентными и порождают язык

 

L(Г7) = {a...ab...b | n,m > 0}

 

Между множествами языков различных типов существует отношение включения:

 

{ L типа 3 } { L типа 2 } { L типа 1 } { L типа 0 }

 

Доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.

Учитывая, что наибольшее практическое применение находят грамматики типа 2 и типа 3, дальнейшее изложение посвящается рассмотрению именно этих типов грамматик.

 

 

КС-грамматика определяет структуру цепочек и позволяет строить цепочки определенного языка. Магазинные автоматы, подобно рассмотренным ранее конечным автоматам, позволяют решать для контекстно-свободных языков задачу распознавания, которая заключается в том, что по заданной цепочке необходимо определить принадлежит ли она заданному языку.

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

Автоматные языки и грамматики. Задача трансляции автоматных языков.

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

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

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

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

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

Для построения компилятора необходимо однозначное и точное задание входного и выходного языков. Такое задание предполагает определение правил построения допустимых конструкций (выражений) языка. Множество таких правил называют синтаксисом языка. Кроме того, задание должно включать описание назначения и смысла каждой конструкции языка. Такое описание называют семантикой языка.

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

Формальные грамматики- Математические модели, использующие представление текстов в виде цепочек символов

КС-грамматика определяет структуру цепочек и позволяет строить цепочки определенного языка. Магазинные автоматы, подобно рассмотренным ранее конечным автоматам, позволяют решать для контекстно-свободных языков задачу распознавания, которая заключается в том, что по заданной цепочке необходимо определить принадлежит ли она заданному языку.

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

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

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

 

Рис. 1.

Головка входной ленты может перемещаться только в одну сторону - вправо или оставаться на месте. Она может выполнять только чтение. Головка вспомогательной ленты способна выполнять как чтение, так и запись, но эти операции связаны с перемещением головки определенным образом:

- при записи головка предварительно сдвигается на одну позицию вверх, а затем символ заносится на ленту,

- при чтении символ, находящийся под головкой считывается с ленты, а затем головка сдвигается на одну позицию вниз, т.о.головка всегда установлена против последнего записанного символа. Позицию, находящуюся в рассматриваемый момент времени под головкой, называют вершиной магазина.

 

Определение. Магазинный автомат М определяется следующей совокупностью семи объектов:

 

M = {P , S , sо , f , F , H , hо }, где

 

P - входной алфавит,

S - алфавит состояний,

sо - начальное состояние,

sо S ,

F - множество конечных состояний, F является подмножеством S,

H - алфавит магазинных символов, записываемых на вспомогательную ленту,

hо - маркер дна, он всегда записывается на дно магазина, hо H,

f - функция переходов

f : {P { ε }} x S x H S x H*,

если М - автомат детерминированный, и

f:{P { ε }} x S x H M( S x H*) ,

если М - автомат недетерминированный.

 

Функция f отображает тройки ( pi, sj, hk) в пары ( sr, υ ), где υ H* и hk - символ в вершине магазина, для детерминированного автомата или в множество пар для недетерминированного автомата.

Эта функция описывает изменение состояния магазинного автомата, происходящее при чтении символа с входной ленты и премещении входной головки.

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

1) функция переходов с пустым символом в качестве входного символа:

 

f0(s, ε, h) = (s', β),

 

которая, независимо от того какой символ находится под читаюшей гловкой входной ленты, предписывает прочитать символ h из вершины магазина, изменить состояние автомата на s' и записать цепочку β в магазин.

 

2) функция переходов с определенным входным символом:

 

f*(s, a, h) = (s', β),

 

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


Дата добавления: 2015-01-29; просмотров: 35; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2022 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты