Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Презентации / Презентация на тему: Формальные грамматики
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

Презентация на тему: Формальные грамматики

библиотека
материалов
Формальные грамматики Подготовила: Ksafo.L  
Формальная грамматика Формальная грамматика или просто грамматика в теории фо...
Виды грамматик Различают порождающие и распознающие (или аналитические) грамм...
Что представляют собой формальные грамматики Введённые в лингвистику американ...
Назначение Назначение грамматики — задание языка. Это задание обязательно дол...
Если язык представляет собой бесконечную совокупность случайным образом набра...
Если посмотреть… С алгоритмической точки зрения грамматики можно подразделить...
1. Распознающие грамматики. Такие грамматики представляют собой устройства (а...
2. Порождающие грамматики. Этот вид устройств используется для порождения цеп...
3. Перечисляющие грамматики. Такие грамматики печатают одну за другой все цеп...
Связь грамматик Интересным представляет вопрос о преобразовании видов граммат...
Можно использовать следующий метод. Получив на вход цепочку, запустить процес...
Конец Спасибо за внимание.
13 1

Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Описание презентации по отдельным слайдам:

№ слайда 1 Формальные грамматики Подготовила: Ksafo.L  
Описание слайда:

Формальные грамматики Подготовила: Ksafo.L  

№ слайда 2 Формальная грамматика Формальная грамматика или просто грамматика в теории фо
Описание слайда:

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

№ слайда 3 Виды грамматик Различают порождающие и распознающие (или аналитические) грамм
Описание слайда:

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

№ слайда 4 Что представляют собой формальные грамматики Введённые в лингвистику американ
Описание слайда:

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

№ слайда 5 Назначение Назначение грамматики — задание языка. Это задание обязательно дол
Описание слайда:

Назначение Назначение грамматики — задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число.

№ слайда 6 Если язык представляет собой бесконечную совокупность случайным образом набра
Описание слайда:

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

№ слайда 7 Если посмотреть… С алгоритмической точки зрения грамматики можно подразделить
Описание слайда:

Если посмотреть… С алгоритмической точки зрения грамматики можно подразделить по способу задания языка. Имеются три основных таких способа (вида грамматик):Распознающие грамматики, Порождающие грамматики, Перечисляющие грамматики.

№ слайда 8 1. Распознающие грамматики. Такие грамматики представляют собой устройства (а
Описание слайда:

1. Распознающие грамматики. Такие грамматики представляют собой устройства (алгоритмы), которым на вход подается цепочка языка, а на выходе устройство печатает «Да», если цепочка принадлежит языку, и «Нет» — в противном случае.

№ слайда 9 2. Порождающие грамматики. Этот вид устройств используется для порождения цеп
Описание слайда:

2. Порождающие грамматики. Этот вид устройств используется для порождения цепочек языков по требованию. Образно говоря, при нажатии кнопки будет сгенерирована некоторая цепочка языка.

№ слайда 10 3. Перечисляющие грамматики. Такие грамматики печатают одну за другой все цеп
Описание слайда:

3. Перечисляющие грамматики. Такие грамматики печатают одну за другой все цепочки языка. Очевидно, что если язык состоит из бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.

№ слайда 11 Связь грамматик Интересным представляет вопрос о преобразовании видов граммат
Описание слайда:

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

№ слайда 12 Можно использовать следующий метод. Получив на вход цепочку, запустить процес
Описание слайда:

Можно использовать следующий метод. Получив на вход цепочку, запустить процесс перечисления цепочек и ждать, напечатает ли перечисляющая грамматика эту цепочку или нет. Если такая цепочка напечатана, то заканчиваем процесс перечисления и печатаем «Да». Если цепочка принадлежит языку, то она обязательно будет напечатана и, таким образом, распознана. Но, если цепочка не принадлежит языку, то процесс распознавания будет продолжаться бесконечно. Программа распознающей грамматики зациклится. В этом смысле мощность распознающих грамматик меньше мощности порождающих и перечисляющих. Это следует иметь ввиду, когда сравнивают порождающие грамматики Хомского и распознающие машины Тьюринга.

№ слайда 13 Конец Спасибо за внимание.
Описание слайда:

Конец Спасибо за внимание.


Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 15.11.2016
Раздел Информатика
Подраздел Презентации
Просмотров133
Номер материала ДБ-355008
Получить свидетельство о публикации
Похожие материалы

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