Context-Free Grammar for {0^n 1^n 2^m 3^m} U {0^n 1^m 2^m 3^n}

Here we show that the union of two given context-free languages, {0^n 1^n 2^m 3^m} Union {0^n 1^m 2^m 3^n}, is also a context-free language. We give a context-free grammar for each of them, and derive a context-free grammar for their union.
Patreon: / easytheory
Facebook: / easytheory
Twitter: / easytheory
If you like this content, please consider subscribing to my channel: / @easytheory
▶ADDITIONAL QUESTIONS◀
1. Would this work for the intersection of the two languages?
2. What about {0^n 1^m 2^n 3^m}?
3. Is this the smallest CFG for this language?
▶SEND ME THEORY QUESTIONS◀
[e-mail]
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental
theory of computer science. It sets out to define, mathematically, what
exactly computation is, what is feasible to solve using a computer,
and also what is not possible to solve using a computer.
The main objective is to define a computer mathematically, without the
reliance on real-world computers, hardware or software, or the plethora
of programming languages we have in use today. The notion of a Turing
machine serves this purpose and defines what we believe is the crux of
all computable functions.
This channel is also about weaker forms of computation, concentrating on
two classes: regular languages and context-free languages. These two
models help understand what we can do with restricted
means of computation, and offer a rich theory using which you can
hone your mathematical skills in reasoning with simple machines and
the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them
are tractable, i.e. we can build efficient algorithms to reason
with objects such as finite automata, context-free grammars and
pushdown automata. For example, we can model a piece of hardware (a circuit)
as a finite-state system and solve whether the circuit satisfies a property
(like whether it performs addition of 16-bit registers correctly).
We can model the syntax of a programming language using a grammar, and
build algorithms that check if a string parses according to this grammar.
On the other hand, most problems that ask properties about Turing machines
are undecidable.
This UA-cam channel will help you see and prove that several tasks involving Turing machines are unsolvable---i.e., no computer, no software, can solve it. For example,
you will see that there is no software that can check whether a
C program will halt on a particular input. To prove something is possible is, of course, challenging.
But to show something is impossible is rare in computer
science, and very humbling.

[@EasyTheory]

Next video! Regular language closure properties: ua-cam.com/video/CuYZIsBSguw/v-deo.html

[@erikabecker8534]

This was a great video, it helped me understand things a lot better!

[@lewkyb]

Great resources. Keep it up! I dunno why more universities don't put more effort into their digital teaching resources...

[@EasyTheory]

luke brown you're very welcome! I saw a need, have lots of experience in doing this, and there's clearly a strong response so far. Onward and upward to getting more views (and hopefully make this my full time job at some point).

[@lowerbound4803]

​@@EasyTheory I hope everything works out in whatever you decide.