Here we create a context-free grammar (CFG) for the set of all strings of the form 0^n 1^m 2^m 3^n, where n, m are at least 0. This is often called "nested pairs" because the n's are on the outside, and the m's are on the inside. We can effectively just make a CFG for the canonical context-free language 0^n 1^n, and modify it to first handle the 0's and 3's, and then once those are done, transfer control to another variable to handle the 1's and 2's, since m and n are unrelated to each other.
Easy Theory Website: 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.
Негізгі бет Context-Free Grammar (CFG) Example: Nested Pairs
Пікірлер: 2