Составить грамматику

@Kortund · Регистрация: 11.06.2022

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

Добрый день, голова горит, спал мало, нужно соорудить грамматику, которая порождает
2^n пар ab
Последнее, к чему я пришел, это
S->ab
S->FF
F->AA
A->S
F->S

Этот вариант явно нерабочий из-за двух последних нетерминалов. Как мне получить искомое?

@3D Homer · 11.06.2022, 20:52

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

нужно соорудить грамматику, которая порождает 2^n пар ab

Грамматики порождают отдельные слова и языки, то есть множества слов. Непонятно, что вы имеете в виду под 2ⁿ парами ab: одно слово (какое?), множество слов или что-то еще. Если нужно породить одно слово w, то простейшая грамматика, которая это делает — это S -> w.

@Kortund · 19.06.2022, 23:16 **[ТС]**

Слово ab.
Нужно сделать так, чтобы я мог получить строку из 2^n слов ab
Если n = 1
То строка abab
Если n = 2
То строка abababab

И так далее

@3D Homer · 19.06.2022, 23:25

Язык $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{(ab)^{2^n}\,|\,n\ge1\}$ не является контекстно-свободным. Контекстно-зависимые грамматики есть на StackExchange. Одна из них взята из примеров 9.4, 9.5 в книге Hopcroft J., Ullman J.D. Introduction to Automata Theory, Languages, and Computations. Addison-Wesley, 1979.

@Kortund 0 / 0 / 0 Регистрация: 11.06.2022 Сообщений: 2
		1
	Составить грамматику 11.06.2022, 10:30. Показов 408. Ответов 3 Метки теория автоматов (Все метки) Добрый день, голова горит, спал мало, нужно соорудить грамматику, которая порождает 2^n пар ab Последнее, к чему я пришел, это S->ab S->FF F->AA A->S F->S Этот вариант явно нерабочий из-за двух последних нетерминалов. Как мне получить искомое? 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	11.06.2022, 20:52	2
	Сообщение от Kortund нужно соорудить грамматику, которая порождает 2^n пар ab Грамматики порождают отдельные слова и языки, то есть множества слов. Непонятно, что вы имеете в виду под 2ⁿ парами ab: одно слово (какое?), множество слов или что-то еще. Если нужно породить одно слово w, то простейшая грамматика, которая это делает — это S -> w. 0

@Kortund 0 / 0 / 0 Регистрация: 11.06.2022 Сообщений: 2
	19.06.2022, 23:16 [ТС]	3
	Слово ab. Нужно сделать так, чтобы я мог получить строку из 2^n слов ab Если n = 1 То строка abab Если n = 2 То строка abababab И так далее 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	19.06.2022, 23:25	4
	Язык $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{(ab)^{2^n}\,\|\,n\ge1\}$ не является контекстно-свободным. Контекстно-зависимые грамматики есть на StackExchange. Одна из них взята из примеров 9.4, 9.5 в книге Hopcroft J., Ullman J.D. Introduction to Automata Theory, Languages, and Computations. Addison-Wesley, 1979. 0