Context-Free Grammar (CFG) Example: {a^i b^j c^k : i at most j+k}
Автор: Easy Theory
Загружено: 2022-08-03
Просмотров: 8500
Here we create a context-free grammar (CFG) for the language {a^i b^j c^k : i is at most j+k}. This is not inherently a hard language, since we take advantage of the fact that i (the number of a's at the front) is at most j+k (the sum of numbers of b's and c's). Therefore, we can match at most one "a" with every "b", and same with the "c"s. We have to use a different variable (at least in this CFG) to process the b's since there is an order on where the b's appear in the string (they're in the middle).
Easy Theory Website: https://www.easytheory.org
Discord: / discord
If you like this content, please consider subscribing to my channel: / @easytheory
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
