Проверить свойства контекстно свободного языка

@Ivan912 · Регистрация: 26.01.2019

Author24 — интернет-сервис помощи студентам

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

Посмотрите пожалуйста правильно ли я решаю его.
Контекстно свободный язык это язык который имеет свойства ,что левая часть это нетерминалы а правая любой символ.
$https://www.cyberforum.ru/cgi-bin/latex.cgi?S->ABCDK A->b|AA B->BB|ab C->b D->DD|a K->KK|b$

У меня получилось составить правило грамматике по этому выражению,значит язык является контекстно свободным и его свойства выполняются?

Ещё такой вопрос какой знак тут стоит между символами ab? получается дано регулярное выражение и стоит знак Конкатенации?

@Бард · 29.08.2019, 08:23

Сообщение от Ivan912

Посмотрите пожалуйста правильно ли я решаю его.

Решаете неправильно, правила грамматики не обеспечивают, например, одинаковое количество пар (ab) и конечных символов b.

Сообщение от Ivan912

получается дано регулярное выражение

Это не регулярное выражение, а описание вида цепочек языка. Кстати, в нём не хватает закрывающей скобки.

@Ivan912 · 30.08.2019, 07:10 **[ТС]**

почему неправильно?S->ABCDK->bBCDK->babCDK->babbDK->babbaK->babbab приминил правила грамматики и получил слово? вроде верно

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

@Бард · 30.08.2019, 08:04

Сообщение от Ivan912

почему неправильно?S->ABCDK->bBCDK->babCDK->babbDK->babbaK->babbab приминил правила грамматики и получил слово?

Если вот так применить, то будет другое, неправильное, слово
S->ABCDK->bBCDK->babCDK->babbDK->babbaK->babbaKK->babbabK->babbabb

Добавлено через 1 минуту

Сообщение от Ivan912

по лемме о накачке (ab)^m+k не равно b^m

ab и без леммы о накачке не равно b

@Ivan912 · 30.08.2019, 08:19 **[ТС]**

можете подсказать как тут лемму применить,смотрел видео но там очень простой пример https://www.youtube.com/watch?... u.be&t=282

Добавлено через 13 минут
¹¹¹

@Бард · 30.08.2019, 08:20

Сообщение от Ivan912

можете подсказать как тут лемму применить

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

@Ivan912 · 30.08.2019, 08:28 **[ТС]**

При накачке b у нас символы b будут увеличиваться символы a останутся в таком же количестве значит язык не кс? вот этого условия достаточно для док-во?

@Бард · 30.08.2019, 08:57

Сообщение от Ivan912

вот этого условия достаточно для док-во?

Нет, конечно, я же выше написал "рассмотреть все возможные варианты цепочек". Разве b единственный возможный вариант?

@Ivan912 · 30.08.2019, 10:24 **[ТС]**

в случае если a^(p+1+k) накачать то у нас символы a растут b не растут.

Интересно как формулировать если взять (ab)^m и b^m накачиваем (ab)^m+k получается у нас ab растут а символ b остаётся неизменным? и наоборот

Добавлено через 33 минуты
зачем все случаи рассматривать разве одного случая недостаточно для док-ва?

@Бард · 30.08.2019, 12:27

Сообщение от Ivan912

зачем все случаи рассматривать разве одного случая недостаточно для док-ва?

То, что один случай накачки не подходит, не доказывает отсутствие других случаев накачки, которые подходят.

@Ivan912 · 30.08.2019, 16:36 **[ТС]**

если 1 случай показывает что язык не регулярный этого достаточно? или все нужно рассмотреть?

@Бард · 30.08.2019, 20:45

Сообщение от Ivan912

если 1 случай показывает что язык не регулярный этого достаточно?

Рассматривался язык КС, откуда взялся регулярный язык?

iifat · 31.08.2019, 10:11

Из теоремы об эквивалентности.

@Ivan912 1 / 1 / 0 Регистрация: 26.01.2019 Сообщений: 92
		1
	Проверить свойства контекстно свободного языка 29.08.2019, 05:22. Показов 1744. Ответов 12 Метки нет (Все метки) Проверить свойства контекстно свободного языка. L=(b^n(ab)^mba^nb^m\|n>=1,m>=1} Точное описания выражения на скриншоте Посмотрите пожалуйста правильно ли я решаю его. Контекстно свободный язык это язык который имеет свойства ,что левая часть это нетерминалы а правая любой символ. $https://www.cyberforum.ru/cgi-bin/latex.cgi?S->ABCDK<br /> A->b\|AA<br /> B->BB\|ab<br /> C->b<br /> D->DD\|a<br /> K->KK\|b$ У меня получилось составить правило грамматике по этому выражению,значит язык является контекстно свободным и его свойства выполняются? Ещё такой вопрос какой знак тут стоит между символами ab? получается дано регулярное выражение и стоит знак Конкатенации? Миниатюры 0

@Бард 165 / 114 / 59 Регистрация: 12.07.2018 Сообщений: 277
	29.08.2019, 08:23	2
	Сообщение было отмечено Ivan912 как решение Решение Сообщение от Ivan912 Посмотрите пожалуйста правильно ли я решаю его. Решаете неправильно, правила грамматики не обеспечивают, например, одинаковое количество пар (ab) и конечных символов b. Сообщение от Ivan912 получается дано регулярное выражение Это не регулярное выражение, а описание вида цепочек языка. Кстати, в нём не хватает закрывающей скобки. 1

@Ivan912 1 / 1 / 0 Регистрация: 26.01.2019 Сообщений: 92
	30.08.2019, 07:10 [ТС]	3
	почему неправильно?S->ABCDK->bBCDK->babCDK->babbDK->babbaK->babbab приминил правила грамматики и получил слово? вроде верно Добавлено через 2 часа 26 минут Кажется понял где моя ошибка рассмотрим два слова (ab)^m и b^m по лемме о накачке (ab)^m+k не равно b^m значит есть протеворечие и язык не контекстно свободный так доказывается? 0

@Бард 165 / 114 / 59 Регистрация: 12.07.2018 Сообщений: 277
	30.08.2019, 08:04	4
	Сообщение от Ivan912 почему неправильно?S->ABCDK->bBCDK->babCDK->babbDK->babbaK->babbab приминил правила грамматики и получил слово? Если вот так применить, то будет другое, неправильное, слово S->ABCDK->bBCDK->babCDK->babbDK->babbaK->babbaKK->babbabK->babbabb Добавлено через 1 минуту Сообщение от Ivan912 по лемме о накачке (ab)^m+k не равно b^m ab и без леммы о накачке не равно b 0

@Ivan912 1 / 1 / 0 Регистрация: 26.01.2019 Сообщений: 92
	30.08.2019, 08:19 [ТС]	5
	можете подсказать как тут лемму применить,смотрел видео но там очень простой пример https://www.youtube.com/watch?... u.be&t=282 Добавлено через 13 минут ¹¹¹ 0

@Бард 165 / 114 / 59 Регистрация: 12.07.2018 Сообщений: 277
	30.08.2019, 08:20	6
	Сообщение от Ivan912 можете подсказать как тут лемму применить Надо рассмотреть все возможные варианты цепочек, которыми может осуществляться накачка, и показать, что они все не подходят. 1

@Ivan912 1 / 1 / 0 Регистрация: 26.01.2019 Сообщений: 92
	30.08.2019, 08:28 [ТС]	7
	При накачке b у нас символы b будут увеличиваться символы a останутся в таком же количестве значит язык не кс? вот этого условия достаточно для док-во? Изображения 0

@Бард 165 / 114 / 59 Регистрация: 12.07.2018 Сообщений: 277
	30.08.2019, 08:57	8
	Сообщение от Ivan912 вот этого условия достаточно для док-во? Нет, конечно, я же выше написал "рассмотреть все возможные варианты цепочек". Разве b единственный возможный вариант? 1

@Ivan912 1 / 1 / 0 Регистрация: 26.01.2019 Сообщений: 92
	30.08.2019, 10:24 [ТС]	9
	в случае если a^(p+1+k) накачать то у нас символы a растут b не растут. Интересно как формулировать если взять (ab)^m и b^m накачиваем (ab)^m+k получается у нас ab растут а символ b остаётся неизменным? и наоборот Добавлено через 33 минуты зачем все случаи рассматривать разве одного случая недостаточно для док-ва? 0

@Бард 165 / 114 / 59 Регистрация: 12.07.2018 Сообщений: 277
	30.08.2019, 12:27	10
	Сообщение от Ivan912 зачем все случаи рассматривать разве одного случая недостаточно для док-ва? То, что один случай накачки не подходит, не доказывает отсутствие других случаев накачки, которые подходят. 0

iifat 2718 / 1772 / 187 Регистрация: 05.06.2011 Сообщений: 5,131
	31.08.2019, 10:11	13
	Из теоремы об эквивалентности. 0

	31.08.2019, 10:11

Опции темы

@Ivan912 1 / 1 / 0 Регистрация: 26.01.2019 Сообщений: 92
	30.08.2019, 16:36 [ТС]	11
	если 1 случай показывает что язык не регулярный этого достаточно? или все нужно рассмотреть? 0

@Бард 165 / 114 / 59 Регистрация: 12.07.2018 Сообщений: 277
	30.08.2019, 20:45	12
	Сообщение от Ivan912 если 1 случай показывает что язык не регулярный этого достаточно? Рассматривался язык КС, откуда взялся регулярный язык? 0

Проверить свойства контекстно свободного языка

Решение