Directory of Linear Bounded Automata Resources

Home > Computers > Computer Science > Theoretical > Automata Theory > Linear Bounded Automata

Linear bounded automata (LBA) are multi-track Turing machines which have only one tape, and this tape is exactly the same length as the input. The family of languages accepted by LBA is the family of context sensitive languages.

Resources in This Category

• Linear Bounded Automata

  http://www.cs.uky.edu/~lewis/texts/theory/automata/lb-auto.pdf
  A course note chapter with a definition of LBA and examples.

• Linear Bounded Automata

  http://www.cs.uiowa.edu/~fleck/PartIIIxpar/sld006.htm
  Set of slides for lectures on LBA.

• Linear Bounded Automaton

  http://en.wikipedia.org/wiki/Linear_bounded_automaton
  Wikipedia article defines LBA and shows their place in the Chomsky hierarchy.

• Linear-bounded Automaton

  http://www.everything2.com/index.pl?node_id=1394039
  Example of construction of an LBA to accept a particular context free language.

Related Categories

• Home > Computers > Computer Science > Theoretical > Formal Language Theory > Context Sensitive Languages

 

Home > Computers > Computer Science > Theoretical > Automata Theory > Linear Bounded Automata

 

---

 

Thanks to DMOZ, which built a great web directory for nearly two decades and freely shared it with the web. About us