Back to Search
Start Over
A finite state probabilistic automaton that accepts a context sensitive language that is not context free
- Source :
- Information and Control. (3):196-208
- Publisher :
- Published by Elsevier Inc.
-
Abstract
- It is known that nonregular languages can be accepted by finite state probabilistic automata. For many years it was not known whether a finite state probabilistic automaton existed that would accept a context sensitive language that is not context free. Such a finite state probabilistic automaton is constructed.
- Subjects :
- Theoretical computer science
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Powerset construction
Computer science
Continuous automaton
General Engineering
Timed automaton
Pushdown automaton
Büchi automaton
ω-automaton
Finite state transducer
Nonlinear Sciences::Cellular Automata and Lattice Gases
Nondeterministic finite automaton with ε-moves
Deterministic finite automaton
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Deterministic automaton
Probabilistic automaton
Quantum finite automata
Two-way deterministic finite automaton
Nondeterministic finite automaton
Generalized nondeterministic finite automaton
State diagram
Context-sensitive language
Engineering(all)
Computer Science::Formal Languages and Automata Theory
Subjects
Details
- Language :
- English
- ISSN :
- 00199958
- Issue :
- 3
- Database :
- OpenAIRE
- Journal :
- Information and Control
- Accession number :
- edsair.doi.dedup.....ae4576fe1714c76a216d872c08b825e9
- Full Text :
- https://doi.org/10.1016/S0019-9958(77)90074-2