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

@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

Точно

Новые блоги и статьи Все статьи Все блоги /
Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .	Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .
Метод с двумя буферами (или double buffering) или ping-pong buffering Hrethgir 02.04.2025 Из ответов LM модели. Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .	На любовном киберфронте Alexander-7 01.04.2025 Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка: «Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .	Как работает Node.js изнутри run.dev 29.03.2025 Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .	Моки в Python: Mock Object Library py-thonny 29.03.2025 Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .	JavaScript: Управление памятью и улучшение производительности run.dev 29.03.2025 В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .

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

Решение

Решение

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

	Построить грамматику, порождающую формальный язык 04.11.2017, 19:55. Показов 13942. Ответов 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