1

As the question states:

I am trying to understand automata. Can every regular language have a linear bounded automaton?

KingFish
  • 8,773
  • 12
  • 53
  • 81
  • Probably be better asked on http://math.stackexchange.com/ – stark Mar 30 '13 at 23:00
  • 1
    Yes. [regular language is subset of almost every formal language](http://stackoverflow.com/questions/13143186/example-of-non-linear-unambiguous-and-non-deterministic-cfl?answertab=votes#tab-top) even for context sensitive language we have Linear Bounded Automato. – Grijesh Chauhan Mar 31 '13 at 06:24

1 Answers1

0

Yes, it is possible to have Linear Bounded Automata for each and every regular languages. Regular languages are proper subset of Context Sensitive Languages. CSL is the language associated with Linear Bounded Automata (LBA). For more information on hierarchy of classes of formal grammars and languages read about Chomsky Hierarchy.

http://en.wikipedia.org/wiki/Chomsky_hierarchy

Deepu
  • 7,592
  • 4
  • 25
  • 47