Languages and Automata

P. M. Cohn
Additional contact information
P. M. Cohn: University College London, Department of Mathematics

Chapter 11 in Further Algebra and Applications, 2003, pp 395-429 from Springer

Abstract: Abstract Many problems in mathematics consist in the calculation of a number or function, and our task may be to classify the different types of calculation that can arise. This can be done very effectively by describing simple machines which could carry out these calculations. Of course the discussion is entirely theoretical (we are not con­cerned with building the machines), but it is no accident that this way of thinking became current in the age of computers. Alan Turing, one of the pioneers of digital computers, used just this method in 1936 to attack decision problems in logic, by introducing the class of `computable functions’, i.e. functions that could be computed on a Turing machine. This development has had many consequences, most of them outside our scope. However, the simplest machines, automata, have an immediate algebraic interpretation. In the algebraic study of languages one uses simple sets of rules (`grammars’) to derive certain types of languages, not mirroring all the complexities of natural languages, but more akin to programming languages. It turns out that these languages can also be described in terms of the machines needed to generate them, and in this chapter we give a brief introduction to algebraic languages and automata.

Keywords: Regular Language; Free Algebra; Free Monoid; Principal Ideal Domain; Power Series Ring (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4471-0039-3_11

Ordering information: This item can be ordered from
http://www.springer.com/9781447100393

DOI: 10.1007/978-1-4471-0039-3_11

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().