CFG and closure properties [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

I am solving one problem and I urgently need a hint to solve one problem:

Use closure under union to show that the following language is context-free:

{a^m bⁿ c^p d^q : n=q or m <= p or m+n=p+q }

Answer 1

Since you haven’t specified what your problem is I will just go through what you need to know.

Closed under union - what does it mean?
If we have a language L and a language S and both are context-free we know that the union of the languages is also context free.

L ∪ S = A Context-free Language

See this for more closure properties of CFLs and you can find proofs of this on the web if you are interested (or you can try to make your own proof).

How can you use this to solve your problem?
You have this language specification (let’s call it L):

L = {a^m bⁿ c^p d^q : n=q or m <= p or m+n=p+q }

You can split this language into 3 other languages:

A = {a^m bⁿ c^p d^q : n = q }
B = {a^m bⁿ c^p d^q : m <= p }
C = {a^m bⁿ c^p d^q : m+n = p+q }

It is easy to see that A ∪ B ∪ C = L.

If you can prove that A, B and C are context-free you can conclude that L is also context-free.

Solution
To determine whether a language is context-free, see this answer. To quote the answer:

First, you should attempt to build a context-free grammar that forms the language in subject. A grammar is context-free if left-hand sides of all productions contain exactly one non-terminal symbol. By definition, if one exists, then the language is context-free.

An equivalent construct would be a pushdown automaton. It's the same as DFA, but with a stack available. It may be easier to build than a grammar.

So if you can build a CFG (or a PDA) for each of the languages A, B and C, you have solved your problem.

Let’s take language A: We need a grammar that generates a string of the form a..b..c..d.. where we must have an equal amount of bs and ds.

S -> AE
A -> Aa  | ε
E -> bEd | C
C -> Cc  | ε

S is the start variable (or non-terminal), ε is the empty string (some people use null symbol ^ but I have always been told to use ε). This grammar should be able to generate the language A and therefore A is a context-free. (Please let me know if anyone detects an error. I haven't created CFGs in a while).

Since this is an exercise I will let you solve the remaining parts, but you should have gotten an idea of how to do it.