Prove that a context-free-grammar is regular

1
votes

I know that to prove that a language is non-regular one can use the pumping-lemma. I think I understand how it works, but when it comes to showing that a context-free-grammar is (or isn't regular) I'm having big problems.

Here is an example of a CFG that I can't understand how to show is regular (or non-regular):

i) S → NP VP
ii) NP → DET N
iii) VP → TV NP
iv) N → N N
v) N → A N
vi) NP → Mary |John
vii) DET → a |the |her |his
viii) TV → bought |loves |misses
ix) N → bike |jersey |mountain |sleeve |brake |
x) A → long |hydraulic |knitted |expensive |steep

My initial guess is that it's not regular because of the fourth rule, but I have no idea how to show it using the pumping-lemma. And if the fourth rule was removed, would it then be regular?

So, my questions are: 1. Is the above grammar regular? What is the approach when trying to show that such a CFG is regular or non-regular? 2. If the recursive rule was removed, is it then regular or not?

I hope someone have some tools that are useful when given such a CFG as the one above, when one wants to show that it's regular or not.

2
context-free-grammarregular-language
If you remove the fourth rule, then the grammar describes a finite language; all finite languages are regular languages. With the fourth rule, the language is still regular since the rule can be rewritten as either right- or left-recursive. The grammar is not regular, if that's important to you, because regular languages have a very strict form. – rici
You can't use the pumping lemma in this case because there are non regular languages that satisfy it. – 1010
If the language is regular, showing a regular grammar (or regex or dfa) that generates the same language would suffice (proving that the languages are the same). – 1010

2 Answers

0
votes

The other answers here are pointing at a nuance that I think you may be missing. A context-free grammar is a set of rules that describe a language, but it itself is not a language. Therefore, asking if the context-free grammar is regular is not a meaningful question - it would be like asking whether the set of all natural numbers is divisible by seventeen.

On the other hand, the question "is the language described by this CFG a regular language?" is a meaningful question to ask, and in this case the answer is yes. To show this, you'll need to figure out what the described language actually looks like, then can either build a DFA/NFA for it, write a regex for it, or write a regular grammar for it. In this particular case, with some thought we can see that the grammar is equivalent to the following regex:

(MJ | DET (A* N)*) TV (MJ | DET (A* N)*)

where MJ, DET, A, N, and TV are shorthands for the choices given by the lists represented in the context-free grammar you provided (with MJ meaning "Mary or John.") Since you can write a regular expression for the language of the grammar, what you have is

  • a context-free grammar,
  • that is not a regular grammar, but
  • which describes a regular language.
0
votes

Wanted to point out that there are two important points to note:

  1. Every regular expression (RE) is also a CFG, however the converse is not true (See here). So unless your questioner knows that the given CFG is also a RE (due to construction of the problem), it may very well not be a RE.
  2. It is impossible to compute given a CFG if it is equivalent to a RE (Undecidable problem) See here

Put together what this gives you is that Am_I_Helpful's answer does not have theoretical support and should not be used.