Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages.

Are there known results about the 'complexity' of regular languages in the CFG context? For example, is it true that every regular language can be generated by an unambiguous LL(1) grammar? Or is something similar true?

The general question above comes from the attempts I made to build a 'simple' grammar generating $L=\{(ab)^i|(ba)^i : i\geq 0\}$. None of the grammars I could build were 'simple'.

share|improve this question

2 Answers 2

A regular grammar is context-free. So regular languages are context-free.

Every regular language has a right regular grammar, which is simply derived from a finaite state automaton for that language.

Every regular language can be recognized by a deterministic finite state au tomaton. From that deterministic FSA you can construct a right regular grammar which is LL(1) since you can decide what to do for parsing by simply looking at the terminal on the rules applicable at any time. There always is only one such rule. Actually you do not even need the pushdown, and use the non-terminal for the states. (this is a bit informal, but it is so simple being formal seems silly).

The key part is producing the deterministic FSA.

So, yes, every regular language can be generated by a LL(1) grammar.

A LL(1) grammar is always unambiguous, as it allows constructing a deterministic push-down automaton. So it is unnecessary to specify that it is unambiguous.

As for your language, it seems strangely defined, and I wonder whether you copied that correctly. What is the "$+$" supposed to mean ?

share|improve this answer
    
I edited my message to change the definition of L. Hope it is accurate now. That's not something i copied, just question i have in mind. –  David Feb 15 at 15:47
    
It is ok. I suppose it means all strings of the form either $(ab)^i$ or $(ba)^i$ for i≥0. Well, try first to get a grammar for the first form only, then for the second. Then try putting them together ... this will be a bit more subtle/fun but not unduly hard. Doing it with right regular grammars should be easiest, unless you prefer a finite state automaton (which is really the same). - - - if you have a further question, add what you have done to your question. –  babou Feb 15 at 16:17

Regular languages are described by regular grammars. These come in two varieties: left-regular and right-regular. Right-regular grammars encode the computation of an NFA: the non-terminals represent the states of the NFA, and the rules encode the transitions. Left-regular grammars do everything in reverse. This is the simple class of grammars you are looking for.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.