Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 14:57 
Не в сети
Начинающий
Зарегистрирован:
03 окт 2014, 14:53
Сообщений: 6
Cпасибо сказано: 0
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 15:21 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 1337
Cпасибо сказано: 72
Спасибо получено:
383 раз в 354 сообщениях
Очков репутации: 105

Добавить очки репутацииУменьшить очки репутации
Вы можете составить конечный автомат, хотя бы недетерминированный, принимающий этот язык? В таком случае сделайте состояния нетерминалами, а каждому переходу [math]q_1\overset{a}{\to}q_2[/math] сопоставьте правило [math]q_1\to aq_2[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 15:49 
Не в сети
Начинающий
Зарегистрирован:
03 окт 2014, 14:53
Сообщений: 6
Cпасибо сказано: 0
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
3D Homer
Подскажите, вот так правильно?
S -> A
A -> abA
A -> cbA
A -> [math]\varepsilon[/math]

И тип формальной грамматики, получается, второй? Исходя из S -> A.
Путаюсь немного.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 16:07 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 1337
Cпасибо сказано: 72
Спасибо получено:
383 раз в 354 сообщениях
Очков репутации: 105

Добавить очки репутацииУменьшить очки репутации
sky2high писал(а):
S -> A
A -> abA
A -> cbA
A -> [math]\varepsilon[/math]
Эта грамматика порождает, в том числе, cbab, что не допускается в исходном языке. После генерирования нескольких ab нужно перейти к другому нетерминалу, из которого уже нельзя будет генерировать ab.

sky2high писал(а):
И тип формальной грамматики, получается, второй? Исходя из S -> A.
Нужно смотреть конкретное определение, но в русской и английской Википедии правила вида [math]A\to B[/math] допускаются в грамматиках типе 3. Главное, что этот язык регулярный, поэтому для него можно (и не так сложно) построить регулярную грамматику. Если какая-то грамматика формально не является регулярной, то это значит, что она составлена неоптимально (с точки зрения иерархии).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 16:32 
Не в сети
Начинающий
Зарегистрирован:
03 окт 2014, 14:53
Сообщений: 6
Cпасибо сказано: 0
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
3D Homer
А Вы бы не могли решение написать?

Может, так...
S->AB
A->abA
B->cbB
A->[math]\varepsilon[/math]
B->[math]\varepsilon[/math]

Цитата:
правила вида A\to B допускаются в грамматиках типе 3

Но ведь тип грамматики определяется по самой сложной (2 или 3 - это 2), а тип языка по самой простой (2 или 3 - это 3).

Цитата:
После генерирования нескольких ab нужно перейти к другому нетерминалу, из которого уже нельзя будет генерировать ab.

А что, если в первоначальном варианте записать не A->cbA, а A->Acb?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 19:07 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 1337
Cпасибо сказано: 72
Спасибо получено:
383 раз в 354 сообщениях
Очков репутации: 105

Добавить очки репутацииУменьшить очки репутации
sky2high писал(а):
Может, так...
S->AB
A->abA
B->cbB
A->[math]\varepsilon[/math]
B->[math]\varepsilon[/math]
Эта грамматика действительно описывает нужный язык, но правило [math]S\to AB[/math] не допускается в регулярных грамматиках (даже обобщенного вида). В регулярных грамматиках в правой части должно быть не более одного нетерминального символа, и во всех правилах терминальные символы должны быть или всегда слева, или всегда справа от нетерминальных.

sky2high писал(а):
Но ведь тип грамматики определяется по самой сложной (2 или 3 - это 2), а тип языка по самой простой (2 или 3 - это 3).
Да. Но в вашей грамматике в третьем посте все правила подходят под обобщенную грамматику третьего типа. Под обобщенной я имею в виду форму, где с одной стороны от нетерминального символа разрешается писать любую цепочку терминальных символов, в том числе пустую, а не только один такой символ.

sky2high писал(а):
А что, если в первоначальном варианте записать не A->cbA, а A->Acb?
Да, грамматика

S -> A
A -> abA
A -> Acb
A -> [math]\varepsilon[/math]

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

S → aA
A → Sb
S → ε

генерирует язык [math]\{a^ib^i\mid i\ge0\}[/math], не являющийся регулярным.

Следующая обобщенная регулярная грамматика генерирует требуемый язык.

S → abS
S → T
T → cbT
T → ε.

Можно написать и строго (т.е. не обобщенную) регулярную грамматику.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 20:00 
Не в сети
Начинающий
Зарегистрирован:
03 окт 2014, 14:53
Сообщений: 6
Cпасибо сказано: 0
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
3D Homer
Цитата:
но правило S\to AB не допускается в регулярных грамматиках (даже обобщенного вида).

Цитата:
порождает нужный язык, но она не регулярная


А почему она должна быть регулярной?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 20:08 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 1337
Cпасибо сказано: 72
Спасибо получено:
383 раз в 354 сообщениях
Очков репутации: 105

Добавить очки репутацииУменьшить очки репутации
Это зависит от задания. В вашем задании в первом посте это требование действительно не значится. Однако мне кажется более элегантным не использовать возможности грамматик, которые не нужны для данного языка, тем более, что это не особенно усложняет задачу.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 20:13 
Не в сети
Начинающий
Зарегистрирован:
03 окт 2014, 14:53
Сообщений: 6
Cпасибо сказано: 0
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
3D Homer
Большое спасибо, что помогли.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю sky2high "Спасибо" сказали:
3D Homer
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Составить грамматику

в форуме Дискретная математика, Теория множеств и Логика

vadim1281

7

761

02 фев 2014, 18:08

Составить грамматику, порождающую формальный язык

в форуме Дискретная математика, Теория множеств и Логика

genia2030

1

212

04 ноя 2017, 19:43

Составить грамматику, порождающую формальный язык

в форуме Дискретная математика, Теория множеств и Логика

veronika123

1

832

07 дек 2014, 13:11

Построить автомат с магазинной памятью и КС-грамматику

в форуме Дискретная математика, Теория множеств и Логика

Whiteboss

0

98

01 май 2018, 20:24

Как составить ряд

в форуме Теория вероятностей

tanyhaftv

6

53

05 ноя 2018, 13:05

Составить ЗЛП

в форуме Исследование операций и Задачи оптимизации

Petr-konev

3

273

02 июн 2014, 20:28

составить уравнение

в форуме Аналитическая геометрия и Векторная алгебра

kristish

13

455

06 дек 2011, 13:03

Как составить уравнение х1

в форуме Алгебра

AnnaLapina

7

350

17 сен 2013, 17:42

Как составить совокупности?

в форуме Математическая статистика и Эконометрика

nataliprokopovich

0

143

19 сен 2015, 19:40

Как под а) составить таблицу?

в форуме Теория вероятностей

AnnaLapina

3

255

19 сен 2013, 17:06


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved