Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 9 ] |
|
Автор | Сообщение | |
---|---|---|
sky2high |
|
|
|
||
Вернуться к началу | ||
3D Homer |
|
|
Вы можете составить конечный автомат, хотя бы недетерминированный, принимающий этот язык? В таком случае сделайте состояния нетерминалами, а каждому переходу [math]q_1\overset{a}{\to}q_2[/math] сопоставьте правило [math]q_1\to aq_2[/math].
|
||
Вернуться к началу | ||
sky2high |
|
|
3D Homer
Подскажите, вот так правильно? S -> A A -> abA A -> cbA A -> [math]\varepsilon[/math] И тип формальной грамматики, получается, второй? Исходя из S -> A. Путаюсь немного. |
||
Вернуться к началу | ||
3D Homer |
|
|
sky2high писал(а): S -> A Эта грамматика порождает, в том числе, cbab, что не допускается в исходном языке. После генерирования нескольких ab нужно перейти к другому нетерминалу, из которого уже нельзя будет генерировать ab.A -> abA A -> cbA A -> [math]\varepsilon[/math] sky2high писал(а): И тип формальной грамматики, получается, второй? Исходя из S -> A. Нужно смотреть конкретное определение, но в русской и английской Википедии правила вида [math]A\to B[/math] допускаются в грамматиках типе 3. Главное, что этот язык регулярный, поэтому для него можно (и не так сложно) построить регулярную грамматику. Если какая-то грамматика формально не является регулярной, то это значит, что она составлена неоптимально (с точки зрения иерархии). |
||
Вернуться к началу | ||
sky2high |
|
|
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? |
||
Вернуться к началу | ||
3D Homer |
|
|
sky2high писал(а): Может, так... Эта грамматика действительно описывает нужный язык, но правило [math]S\to AB[/math] не допускается в регулярных грамматиках (даже обобщенного вида). В регулярных грамматиках в правой части должно быть не более одного нетерминального символа, и во всех правилах терминальные символы должны быть или всегда слева, или всегда справа от нетерминальных.S->AB A->abA B->cbB A->[math]\varepsilon[/math] B->[math]\varepsilon[/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 → ε. Можно написать и строго (т.е. не обобщенную) регулярную грамматику. |
||
Вернуться к началу | ||
sky2high |
|
|
3D Homer
Цитата: но правило S\to AB не допускается в регулярных грамматиках (даже обобщенного вида). Цитата: порождает нужный язык, но она не регулярная А почему она должна быть регулярной? |
||
Вернуться к началу | ||
3D Homer |
|
|
Это зависит от задания. В вашем задании в первом посте это требование действительно не значится. Однако мне кажется более элегантным не использовать возможности грамматик, которые не нужны для данного языка, тем более, что это не особенно усложняет задачу.
|
||
Вернуться к началу | ||
sky2high |
|
|
3D Homer
Большое спасибо, что помогли. |
||
Вернуться к началу | ||
За это сообщение пользователю sky2high "Спасибо" сказали: 3D Homer |
||
[ Сообщений: 9 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Составить грамматику, порождающую формальный язык | 1 |
1520 |
07 дек 2014, 13:11 |
|
Составить грамматику, порождающую формальный язык | 1 |
1148 |
04 ноя 2017, 19:43 |
|
Построить грамматику | 5 |
85 |
24 дек 2023, 16:14 |
|
Построить грамматику | 1 |
177 |
25 сен 2019, 14:04 |
|
Построить праволинейную грамматику | 0 |
193 |
04 сен 2019, 06:34 |
|
Построить кс грамматику порождающе | 1 |
182 |
31 авг 2019, 23:13 |
|
Построить автомат с магазинной памятью и КС-грамматику | 0 |
318 |
01 май 2018, 20:24 |
|
Как составить ряд
в форуме Теория вероятностей |
6 |
149 |
05 ноя 2018, 13:05 |
|
Составить ЗЛП | 3 |
441 |
02 июн 2014, 20:28 |
|
Составить выражение
в форуме Алгебра |
2 |
135 |
03 сен 2021, 00:21 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 23 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |