Online citations, reference lists, and bibliographies.

Formal Language Theory: Basics

A. Meduna, O. Soukup
Published 2017 · Computer Science

Cite This
Download PDF
Analyze on Scholarcy
Share
This chapter covers the basics of formal language theory. It covers all the notions that are necessary to follow the rest of this book. Apart from the classical rudiments, however, the chapter covers several lesser-known areas of this theory, such as parallel grammars, because these areas are also needed to fully grasp some upcoming topics discussed in this book. The chapter consists of four sections.
This paper references
10.2307/2371809
Formal Reductions of the General Combinatorial Decision Problem
E. Post (1943)
10.2307/2269326
A Note on the Entscheidungsproblem
A. Church (1936)
10.1007/978-1-4613-8476-2
The Algorithmic Beauty of Plants
P. Prusinkiewicz (1990)
10.2307/2316720
Theory of Recursive Functions and Effective Computability
Jr. Hartley Rogers (1969)
10.1007/BF00264281
On the generative power of regular pattern grammars
J. Kleijn (2004)
10.1016/S0019-9958(59)90362-6
On Certain Formal Properties of Grammars
Noam Chomsky (1959)
10.1109/TIT.1956.1056813
Three models for the description of language
Noam Chomsky (1956)
10.1007/978-1-4471-0501-5
Automata and Languages
A. Meduna (2000)
10.2307/2371045
An Unsolvable Problem of Elementary Number Theory
A. Church (1936)
L-systems: from the Theory to Visual Models of Plants
P. Prusinkiewicz (2001)
10.1007/978-1-84628-877-7_3
Formal languages
A. Salomaa (1987)
10.1007/978-3-642-95486-3
The Book of L
G. Rozenberg (1986)
10.1007/978-94-017-3477-6
The Theory of Algorithms
A. A. Markov (1954)
10.1201/b16376
Formal Languages and Computation: Models and Their Applications
A. Meduna (2014)
Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity
A. Meduna (2004)
10.1145/321386.321403
One-way stack automata
S. Ginsburg (1967)
Regulated Pushdown Automata
A. Meduna (2000)
10.1112/plms/s2-42.1.230
On computable numbers, with an application to the Entscheidungsproblem
A. Turing (1937)
10.1080/0020716031000070616
Simultaneously One-Turn Two-Pushdown Automata
A. Meduna (2003)



Semantic Scholar Logo Some data provided by SemanticScholar