2

I am not asking for the solution, it's an assignment, but I didn't see any question like that, I am asking for what's does it means:

The question:

Create a Regular Grammar that generates the same language which is generated by the following Context Free Grammar:

G = {{S,X,Y}, {a,b,c}, S, P} Where P is:

S ----> aaS
S ----> bX
X ----> cYb

X ----> cb
Y ----> bbY
Y ----> bb

Does it means to generate the language? I am confused about creating RG from CFG.

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
Caffe Latte
  • 1,693
  • 1
  • 14
  • 32
  • 1
    Class of regular language is subset of class of context free *language* that means your can write context free *grammar* for a regular language (for example your grammar). Your grammar G is context free but language is regular (actually very regular languages is context free but reverse is not true). For the language genrated by your grammar = L(G) you can also write regular grammar that is Either [left-liner or right-liner grammar](http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars/13945932#13945932) You are aked to write that – Grijesh Chauhan Sep 12 '13 at 05:29
  • @GrijeshChauhan Thanks, and +1 for the link, hope this comment was as answer to upvote it. – Caffe Latte Sep 13 '13 at 06:57
  • 1
    Thanks your +1 I got nice badge :), let me know if you have doubts. – Grijesh Chauhan Sep 13 '13 at 07:02

1 Answers1

1

Good question and this topic is worth knowing. I would seek help from a TA or something of that nature. The study of finite automaton is vital to a successful career in computer science in my opinion.

The languages that can be represented by CFGs and RLs are very different and the question is designed to help you understand that.

I don't really like the use of the word "generate", "accept" is more appropriate. Find the RL that accepts the same strings as CFG given below is how I would write the question.

Keep in mind that a regular language is equivalent to a finite state machine, so you can work in this by drawing one that accepts the stings accepted by the given CFG.

Find the answer to your question, but doing so here is kind of the wrong place to do so.

now to do this problem for fun...

Pete B.
  • 3,188
  • 6
  • 25
  • 38
  • +1,Thanks, great hint from you. I am thinking like that: first, find the language for the given CFG, then I must find the RG that accepts the same language. – Caffe Latte Sep 09 '13 at 20:41