Построить грамматику, порождающую формальный язык

@boode1 · Регистрация: 04.11.2017

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

L(G) = {(ab)^n (cb)^m | n, m>=0}

1) Построить грамматику, порождающую формальный язык.
2) Построить цепочку языка по грамматике.
3) Построить дерево вывода (левосторонний и правосторонний вывод) для этой цепочки. Эквивалентны ли они?
4) Определить тип формальной грамматики и языка по классификации Хомского.

Помогите, пожалуйста! Буду признателен!

@Fatosha · 05.11.2017, 00:28

1)
$https://www.cyberforum.ru/cgi-bin/latex.cgi?S -> AB|\varepsilon<br /> \\<br /> A -> abA|\varepsilon<br /> \\<br /> B -> cbB|\varepsilon$

2) $https://www.cyberforum.ru/cgi-bin/latex.cgi?S -> AB -> abAB -> ababAB -> ababB -> ababcbB -> ababcb$
3) Дерево построишь сам, таже самая цепочка. Цепочки эквивалентны
4) Второй тип

@boode1 · 05.11.2017, 10:46 **[ТС]**

Подскажите, как сделать левосторонний и правосторонний вывод?
Чем они вообще отличаются и как их делать?

Сообразить никак не могу, какие переходы брать ...

@Fatosha · 05.11.2017, 10:57

Ну для левого вывода надо всегда разворачивать самый левый нетерминал. В 2 пункте всегда разворачивал А, потом развернул B.
В правостороннем аналогично, только для правогонетерминала.

@boode1 · 05.11.2017, 11:01 **[ТС]**

Т.е.

S->AB->AcbB->Acb->abAcb->ababAcb->ababcb

Так?

@Fatosha · 05.11.2017, 11:10

Точно

Новые блоги и статьи Все статьи Все блоги /
Миграция монолита в Event-Driven микросервисную архитектуру на C# stackOverflow 11.04.2025 Монолитная архитектура – классический подход к разработке программного обеспечения. Это приложение, построенное как единое целое, где все компоненты тесно связаны между собой. Большинство проектов. . .	Go в Kubernetes: Управление ресурсами golander 11.04.2025 Разработчики Go-приложений в Kubernetes часто сталкиваются с неожиданными проблемами производительности и даже внезапными отказами контейнеров. Причина этого кроется в особенностях взаимодействия. . .	Агрегаты и сущности в DDD микросервисах Javaican 10.04.2025 Разработка современных программных систем часто приводит на распутье: монолит или микросервисы? Даже при выборе микросервисной архитектуры многие команды сталкиваются с проблемой правильного. . .	Многопоточность в C#: Task и параллельное программирование UnmanagedCoder 10.04.2025 Современные процессоры уже давно перестали наращивать тактовую частоту в пользу увеличения количества ядер. Это создало интересную ситуацию: разработчики, привыкшие к последовательному. . .	Линейное решение нелинейной задачи будет иметь приблизительный результат вычисления для метода обработки данных из double buffering. Hrethgir 10.04.2025 Вообще изначально я пренебрёг квадратурой числа, но потом понял, что для вычисления приблизительного значения - сгодится, формулу можно будет корректировать по ходу. Это потому что прямое соотношение. . .
Переменные в Python py-thonny 10.04.2025 Переменная в программировании — это символическое имя, связанное с областью памяти, в которой хранится значение. Она позволяет получать доступ к данным через понятные человеку идентификаторы, а не. . .	Многопоточность в C#: Task и асинхронные операции UnmanagedCoder 10.04.2025 Многопоточность позволяет выполнять несколько операций одновременно, что важно для решения двух основных задач: повышения скорости выполнения вычислительно-сложных операций и сохранения отзывчивости. . .	Запуск контейнеров Docker на ARM64 Mr. Docker 09.04.2025 Появление таких решений, как Apple M1/ M2, AWS Graviton, Ampere Altra и Raspberry Pi, сделало использование ARM-систем обыденностью для многих разработчиков и DevOps-инженеров. При этом Docker,. . .	Vue SFC компонент на PHP с Fusion Jason-Webb 09.04.2025 PHP на сервере и JavaScript на клиенте — классическое сочетание, которое, несмотря на свою эффективность, создает определенный когнитивный диссонанс при разработке. В этом контексте появляются. . .	TypeScript vs JavaScript: Отличия и когда что использовать Reangularity 09.04.2025 JavaScript появился в 1995 году как творение Брендана Эйха и быстро стал основой интерактивности в вебе. За свою историю он прошел путь от простого языка для манипуляций с DOM до полноценной. . .

Построить грамматику, порождающую формальный язык

Решение

Решение

@boode1 2 / 2 / 2 Регистрация: 04.11.2017 Сообщений: 88

	Построить грамматику, порождающую формальный язык 04.11.2017, 19:55. Показов 13970. Ответов 5 Метки нет (Все метки) L(G) = {(ab)^n (cb)^m \| n, m>=0} 1) Построить грамматику, порождающую формальный язык. 2) Построить цепочку языка по грамматике. 3) Построить дерево вывода (левосторонний и правосторонний вывод) для этой цепочки. Эквивалентны ли они? 4) Определить тип формальной грамматики и языка по классификации Хомского. Помогите, пожалуйста! Буду признателен! 0

@Fatosha 2 / 2 / 2 Регистрация: 12.10.2013 Сообщений: 168
	05.11.2017, 00:28
	Сообщение было отмечено boode1 как решение Решение 1) $https://www.cyberforum.ru/cgi-bin/latex.cgi?S -> AB\|\varepsilon<br /> \\<br /> A -> abA\|\varepsilon<br /> \\<br /> B -> cbB\|\varepsilon$ 2) $https://www.cyberforum.ru/cgi-bin/latex.cgi?S -> AB -> abAB -> ababAB -> ababB -> ababcbB -> ababcb$ 3) Дерево построишь сам, таже самая цепочка. Цепочки эквивалентны 4) Второй тип 2

@boode1 2 / 2 / 2 Регистрация: 04.11.2017 Сообщений: 88
	05.11.2017, 10:46 [ТС]
	Подскажите, как сделать левосторонний и правосторонний вывод? Чем они вообще отличаются и как их делать? Сообразить никак не могу, какие переходы брать ... 0

@Fatosha 2 / 2 / 2 Регистрация: 12.10.2013 Сообщений: 168
	05.11.2017, 10:57
	Сообщение было отмечено boode1 как решение Решение Ну для левого вывода надо всегда разворачивать самый левый нетерминал. В 2 пункте всегда разворачивал А, потом развернул B. В правостороннем аналогично, только для правогонетерминала. 0

@boode1 2 / 2 / 2 Регистрация: 04.11.2017 Сообщений: 88
	05.11.2017, 11:01 [ТС]
	Т.е. S->AB->AcbB->Acb->abAcb->ababAcb->ababcb Так? 0

@Fatosha 2 / 2 / 2 Регистрация: 12.10.2013 Сообщений: 168
	05.11.2017, 11:10
	Точно 0