Доказать, что язык нерегулярный

@Anriuser · Регистрация: 18.10.2013

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

Довести что язык $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left[0^m 10^m \mid m=0,1,2... \right]$ нерегулярный

@3D Homer · 30.09.2017, 17:02

Можно воспользоваться леммой о накачке (о разрастании, pumping lemma). Для этого нужно прочитать несколько примеров применения этой леммы.

@Anriuser · 30.09.2017, 18:09 **[ТС]**

незнаю я этого дайте ответ просто

@3D Homer · 30.09.2017, 18:12

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

дайте ответ просто

Я только даю подсказки.

@Anriuser · 30.09.2017, 19:02 **[ТС]**

Почему вы просто не дадите мне решение, для вас же это 3 минуты сделать.

@Anriuser · 01.10.2017, 20:24 **[ТС]**

Нерегулярный потомучто не существует регулярной граматики, которая б порождала этот язык.

@3D Homer · 01.10.2017, 20:38

Доказать несуществование грамматики не совсем просто. Проще доказать, что не выполняется необходимое свойство регулярных языков, например, лемма о разрастании. Но у этой леммы не совсем простое условие, в котором нужно разбираться. После разбирательства очень желательно посмотреть несколько примеров применения этой леммы. Я могу написать решение, но без понимания утверждения леммы и его отрицания (вам нужно доказать отрицание для данного языка, и поскольку лемма дает необходимое условие регулярности, этим будет показано, что язык нерегулярный) вы сможете только переписать это решение, а не объяснить его.

@Anriuser · 01.10.2017, 20:49 **[ТС]**

С таким раскладом я лучше напишу свой вариант а вы мне дайте ответ на то что я реально не смогу сделать сам)

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
		1
	Доказать, что язык нерегулярный 30.09.2017, 15:03. Показов 4814. Ответов 7 Метки нет (Все метки) Довести что язык $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left[0^m 10^m \mid m=0,1,2... \right]$ нерегулярный 0

@3D Homer $Эксперт по математике/физике$ 4945 / 3564 / 1149 Регистрация: 01.09.2014 Сообщений: 9,649
	30.09.2017, 17:02	2
	Можно воспользоваться леммой о накачке (о разрастании, pumping lemma). Для этого нужно прочитать несколько примеров применения этой леммы. 0

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	30.09.2017, 18:09 [ТС]	3
	незнаю я этого дайте ответ просто 0

@3D Homer $Эксперт по математике/физике$ 4945 / 3564 / 1149 Регистрация: 01.09.2014 Сообщений: 9,649
	30.09.2017, 18:12	4
	Сообщение от Anriuser дайте ответ просто Я только даю подсказки. 1

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	30.09.2017, 19:02 [ТС]	5
	Почему вы просто не дадите мне решение, для вас же это 3 минуты сделать. 0

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	01.10.2017, 20:24 [ТС]	6
	Нерегулярный потомучто не существует регулярной граматики, которая б порождала этот язык. 0

@3D Homer $Эксперт по математике/физике$ 4945 / 3564 / 1149 Регистрация: 01.09.2014 Сообщений: 9,649
	01.10.2017, 20:38	7
	Сообщение было отмечено Anriuser как решение Решение Доказать несуществование грамматики не совсем просто. Проще доказать, что не выполняется необходимое свойство регулярных языков, например, лемма о разрастании. Но у этой леммы не совсем простое условие, в котором нужно разбираться. После разбирательства очень желательно посмотреть несколько примеров применения этой леммы. Я могу написать решение, но без понимания утверждения леммы и его отрицания (вам нужно доказать отрицание для данного языка, и поскольку лемма дает необходимое условие регулярности, этим будет показано, что язык нерегулярный) вы сможете только переписать это решение, а не объяснить его. 1

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	01.10.2017, 20:49 [ТС]	8
	С таким раскладом я лучше напишу свой вариант а вы мне дайте ответ на то что я реально не смогу сделать сам) 0

Опции темы

Доказать, что язык нерегулярный

Решение