Context Free Grammar to Regular Expression?

I want to learn whether I can create regular expressions from the given Context Free Grammar. I found some examples that can be translated to regular expressions. However, all of them were like this: "S-> aB | bC". Whereas my example is like: "S-> AB | BC". Here is my example:

Can I create RE's from this? What is the reason? I want to fully understand why I can and why I cannot. Thank you.

The set of all regular languages is a subset of context free languages. So if you have a context free grammar (CFG) that generates a regular languages, you most certainly can convert it to a regular expression (RE), regular grammar (RG), or finite automata (FA).

Before I go further with your example, I will simplify it so that we only deal with 3 terminals (instead of 8). In the example below, the terminals a,b,c will be represented by the single terminal a, the terminals x,y,z will be represented by x, and the terminals p,q will be represented by p.

S -> N V
N -> a N | N N | N a | x
V -> N V | p

There is no real procedure in converting it, so we will take it step by step. First we need to see what kinds of strings the variable N can produce.

We can see that for every N introduced, it terminates with x. The a's can be on either side of x and repeat as many times as needed. This entire pattern can be repeated as many times as needed, but be produced at least once. So N generates the same strings as $(a^x^+a^)^+$ RE.

Next we look at V. It can produce any amount of N's but must terminate with a single p. So we have $((a^x^+a^)^+)^p = (a^x^+a^)^p$.

Finally, S produces NV which is similar to our RE for V. Note that there is at least one N produced. So that CFG is converted to $(a^x^+a^)^+p$.

To put it in terms of your original grammar, it would look something like this $((a|b|c)^(x|y|z)^+(a|b|c)^)^+(p|q)$. Again, because of the amount of terminals in the original grammar, it is easier to simply things to help see the pattern the grammar is actually showing.

As a disclaimer, this is not a proof, but it shows the reasoning as to how I created an RE from the CFG you provided. To know if this is correct, you would need to know the exact language the CFG produces. Unfortunately, the grammar is not easily recognizable.

I used the following CFG Developer tool to help see a pattern from your grammar.

StackExchange Computer Science Q#133511, answer score: 6