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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 03 окт 2014, 15:21 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
Вы можете составить конечный автомат, хотя бы недетерминированный, принимающий этот язык? В таком случае сделайте состояния нетерминалами, а каждому переходу [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 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
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 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
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 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

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

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

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

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

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

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

veronika123

1

1520

07 дек 2014, 13:11

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

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

genia2030

1

1148

04 ноя 2017, 19:43

Построить грамматику

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

carti539

5

85

24 дек 2023, 16:14

Построить грамматику

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

Alexander132

1

177

25 сен 2019, 14:04

Построить праволинейную грамматику

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

Alexander132

0

193

04 сен 2019, 06:34

Построить кс грамматику порождающе

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

Alexander132

1

182

31 авг 2019, 23:13

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

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

Whiteboss

0

318

01 май 2018, 20:24

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

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

tanyhaftv

6

149

05 ноя 2018, 13:05

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

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

Petr-konev

3

441

02 июн 2014, 20:28

Составить выражение

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

dikarka2004

2

135

03 сен 2021, 00:21


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



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

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


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

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

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

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