1 or 2 right hand side variable in Context free language

641 views Asked by At

I have 2 questions to ask and I have some ideas about it also.

1) X-Context free grammer(X-CFG) with 1 terminal or variable at the right hand side of every rule.

2) Y-CFG with 2 terminal or variable at the right hand side of every rule.

Questions:

a) Do they generate any non-regular languages? Prove.

b) Do they generate all regular languages? Prove.

Answers:

a) I think for X-CFG, they can not generate any non regular because it can can only generate finite number of strings so they cant generate any non regular languages.

b) There are infinite number of regular languages like a^* . We can nor generate infinite strings with CFG, so we can say that it can not generate all regular languages.

Am I right?

I have no idea about question b.

1

There are 1 answers

5
fjoe On BEST ANSWER

Consider the Y-CFG:

S → aA
S → ab
A → Sb

Is this not a Y-CFG that satisfies your constraints and generates a non-regular language? an bn such that n >= 1

Also see this as it states:

Every regular grammar is context-free, but not all context-free grammars are regular. And explains a little why with an example to help grasp it.

So I believe both of your answers are wrong if I understood the question correctly.

UPDATE

Every regular grammar is context-free. So then the question is can we define all CFG's using 2 variables (t is terminal and N is non-terminal):

S → SS
S → t
S → N
S → tN
S → Nt

Therefore we can define things that terminate, things that grow out from multiple starting strings, things that grow in front and things that grow in back. Which is every case in a CFG. So I would say yes you can generate all regular languages.