Finite Automation

Question

A language L is accepted by finite automata if and only if it is

• A. Right linear
• B. Primitive Recursive
• C. Context Sensitive
• D. Recursive

Answer 1

Answer is A).

A language L is regular if and only if L can be generated by a regular grammar. 

The regular grammar is also called a right-linear grammar  or left linear grammar.

If we mix left-linear and right-linear production rules in a single grammar, the result will not necessarily be a regular grammer .

Comments

Are you saying right linear and left linear are synonyms?

---

@Arjun sir,

No, i am not saying this. Left linear grammars are not good. They are very complex and not easy to be parsed. Right linear grammars are much simpler and easy to parse . They don't create unwanted parsing errors. But , yes we can convert left linear grammar to a right linear grammar. Every left-linear grammar can be converted to an equivalent right-linear grammar. Right-linear grammars are regular grammars and hence generate regular languages . Hence, every left-linear grammar generates a regular language .