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

@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

Точно

Новые блоги и статьи Все статьи Все блоги /
Обмен данными в микросервисной архитектуре ArchitectMsa 06.04.2025 Когда разработчики начинают погружаться в мир микросервисов, они часто сталкиваются с парадоксальным правилом: "два сервиса не должны делить один источник данных". Эта мантра звучит повсюду в. . .	PostgreSQL в Kubernetes: Автоматизация обслуживания с CNPG Mr. Docker 06.04.2025 Администраторы баз данных сталкиваются с целым рядом проблем при обслуживании PostgreSQL в Kubernetes: как обеспечить правильную репликацию данных, как настроить автоматическое переключение при. . .	Async/await в TypeScript run.dev 06.04.2025 Асинхронное программирование — это подход к разработке программного обеспечения, при котором операции выполняются независимо друг от друга. В отличие от синхронного выполнения, где каждая последующая. . .	Многопоточность в C#: Синхронизация потоков UnmanagedCoder 06.04.2025 Многопоточное программирование стало неотъемлемой частью разработки современных приложений на C#. С появлением многоядерных процессоров возможность выполнять несколько задач параллельно значительно. . .	TypeScript: Классы и конструкторы run.dev 06.04.2025 TypeScript, как статически типизированный язык, построенный на основе JavaScript, привнес в веб-разработку новый уровень надежности и структурированности кода. Одним из важнейших элементов этой. . .
Многопоточное программирование: Rust против C++ golander 06.04.2025 C++ существует уже несколько десятилетий и его поддержка параллелизма постепенно наращивалась со временем. Начиная с C++11, язык получил стандартную библиотеку для работы с потоками, а в последующих. . .	std::vector в C++: от основ к оптимизации производительности NullReferenced 05.04.2025 Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .	Реляционная модель и правила Кодда: фундамент современных баз данных Codd 05.04.2025 Конец 1960-х — начало 1970-х годов был периодом глубоких трансформаций в области хранения и обработки данных. На фоне растущих потребностей бизнеса и правительственных структур существовавшие на тот. . .	Асинхронные операции в Django с Celery py-thonny 05.04.2025 Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .	Использование кэшей CPU: Максимальная производительность в Go golander 05.04.2025 Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .

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

Решение

Решение

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

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