Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 30.08.2019, 04:54   #1
Ivan912
Пользователь
 
Регистрация: 26.01.2019
Сообщений: 32
По умолчанию Проверить свойства контекстно свободного языка

Проверить свойства контекстно свободного языка.
L=(b^n(ab)^m*ba^n*b^m|n>=1,m>=1}
Точное описания выражения на скриншоте

Посмотрите пожалуйста правильно ли я решаю его.
Контекстно свободный язык это язык который имеет свойства ,что левая часть это нетерминалы ,а правая любой символ.
Цитата:
S−>ABCDK
A−>b|AA
B−>BB|ab
C−>b
D−>DD|a
K−>KK|b
У меня получилось составить правило грамматике по этому выражению,значит язык является контекстно свободным и его свойства выполняются?

пример вывода цепочки по этой грамматики которая у меня получилась
Цитата:
S−>ABCDK−>bBCDK−>babCDK−>babbDK−>ba bbaK−>babbab
Изображения
Тип файла: jpg Screenshot_3.jpg (8.5 Кб, 83 просмотров)
Ivan912 вне форума Ответить с цитированием
Старый 30.08.2019, 07:10   #2
Ivan912
Пользователь
 
Регистрация: 26.01.2019
Сообщений: 32
По умолчанию

Кажется понял где моя ошибка рассмотрим два слова (ab)^m и b^m по лемме о накачке (ab)^m+k не равно b^m значит есть протеворечие и язык не контекстно свободный так доказывается?
Ivan912 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
[Идея] Приложение-каталог свободного ПО preacherby Свободное общение 8 12.11.2014 17:56
контекстно свободная грамматика(компиляторы) alex1001 Visual C++ 0 18.03.2013 16:01
размер свободного места на диске detalik Помощь студентам 5 22.10.2012 19:30
Как проверить количество свободного и занятого места на логическом диске SeRhy Общие вопросы Delphi 4 09.06.2008 15:39