Найти язык, порожденный грамматикой

@artem55555p · Регистрация: 27.02.2015

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

Здравствуйте. Можете объяснить пошагово как решать данную задачу, примеров нигде толком нет:

@artem55555p · 13.06.2017, 12:49 **[ТС]**

Как я понял, мне нужно, построить 3-4 цепочки из этого и написать формулу
типо (a^nb^n)*
но как это сделать?

@3D Homer · 13.06.2017, 13:14

Занумеруйте правила, скажем, по строчкам. Выпишите 10 примеров выводов, то есть последовательностей правил с получившимися строками из a, b. Это может дать идею общего вида порожденных строк.

Данная грамматика праволинейная, и ее легко превратить в НКА. Нетерминалы становятся состояниями, а правило, например, A -> aB превращается в переход из состояния A в B при прочтении символа a. Возможно, по автомату записать язык легче.

@artem55555p · 13.06.2017, 13:15 **[ТС]**

дело в том, что я не знаю как строить их. можете объяснить?

@3D Homer · 13.06.2017, 13:19

Нужно читать рекомендованную литературу. Зайдите на этот сайт и ищите

Жильцова Л.П., Смирнова Т.Г. Основы теории контекстно-свободных языков в примерах и задачах: учебно-методическое пособие

@artem55555p 29 / 0 / 0 Регистрация: 27.02.2015 Сообщений: 231
		1
	Найти язык, порожденный грамматикой 13.06.2017, 12:45. Показов 1117. Ответов 4 Метки нет (Все метки) Здравствуйте. Можете объяснить пошагово как решать данную задачу, примеров нигде толком нет: 0

@artem55555p 29 / 0 / 0 Регистрация: 27.02.2015 Сообщений: 231
	13.06.2017, 12:49 [ТС]	2
	Как я понял, мне нужно, построить 3-4 цепочки из этого и написать формулу типо (a^nb^n)* но как это сделать? 0

@3D Homer $Эксперт по математике/физике$ 4951 / 3569 / 1150 Регистрация: 01.09.2014 Сообщений: 9,651
	13.06.2017, 13:14	3
	Занумеруйте правила, скажем, по строчкам. Выпишите 10 примеров выводов, то есть последовательностей правил с получившимися строками из a, b. Это может дать идею общего вида порожденных строк. Данная грамматика праволинейная, и ее легко превратить в НКА. Нетерминалы становятся состояниями, а правило, например, A -> aB превращается в переход из состояния A в B при прочтении символа a. Возможно, по автомату записать язык легче. 0

@artem55555p 29 / 0 / 0 Регистрация: 27.02.2015 Сообщений: 231
	13.06.2017, 13:15 [ТС]	4
	дело в том, что я не знаю как строить их. можете объяснить? 0

@3D Homer $Эксперт по математике/физике$ 4951 / 3569 / 1150 Регистрация: 01.09.2014 Сообщений: 9,651
	13.06.2017, 13:19	5
	Нужно читать рекомендованную литературу. Зайдите на этот сайт и ищите Жильцова Л.П., Смирнова Т.Г. Основы теории контекстно-свободных языков в примерах и задачах: учебно-методическое пособие 0