Дискуссионный математический форумМатематический форум
Математический форум 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
Сообщений: 1435
Cпасибо сказано: 80
Спасибо получено:
412 раз в 383 сообщениях
Очков репутации: 120

Добавить очки репутацииУменьшить очки репутации
Вы можете составить конечный автомат, хотя бы недетерминированный, принимающий этот язык? В таком случае сделайте состояния нетерминалами, а каждому переходу [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
Сообщений: 1435
Cпасибо сказано: 80
Спасибо получено:
412 раз в 383 сообщениях
Очков репутации: 120

Добавить очки репутацииУменьшить очки репутации
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
Сообщений: 1435
Cпасибо сказано: 80
Спасибо получено:
412 раз в 383 сообщениях
Очков репутации: 120

Добавить очки репутацииУменьшить очки репутации
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
Сообщений: 1435
Cпасибо сказано: 80
Спасибо получено:
412 раз в 383 сообщениях
Очков репутации: 120

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

Вернуться к началу
 Профиль  
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 ]

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

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

vadim1281

7

794

02 фев 2014, 18:08

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

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

genia2030

1

270

04 ноя 2017, 19:43

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

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

veronika123

1

878

07 дек 2014, 13:11

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

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

Whiteboss

0

107

01 май 2018, 20:24

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

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

Petr-konev

3

275

02 июн 2014, 20:28

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

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

tanyhaftv

6

59

05 ноя 2018, 13:05

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

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

FunDoren

9

399

21 дек 2013, 22:47

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

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

kristish

13

480

06 дек 2011, 13:03

Составить отрицание

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

NEW

11

709

17 ноя 2013, 15:40

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

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

AnnaLapina

7

368

17 сен 2013, 17:42


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



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

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


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

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

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

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