<p>I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars?  If so, are markov decision processes thus solvable by nondeterministic finite automota?  Thank you, and my apologies in advance if this question is invalid/makes no sense.</p>

CC BY-SA 3.0
2017-07-24T21:08:37.580Z
How do you define the *language* accepted by an MDP?
Aryeh
CC BY-SA 3.0
2017-07-25T16:04:13.993Z
You may want to read https://en.wikipedia.org/wiki/Probabilistic_automaton
xavierm02
<fl.formal-languages><computability><automata-theory><regular-language><grammars>
Relation between MDPs and non-deterministic finite automatons
nanogru
# Relation between MDPs and non-deterministic finite automatons

(Asked by: username_0 on 2017-07-24)

I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus solvable by nondeterministic finite automota? Thank you, and my apologies in advance if this question is invalid/makes no sense.

**Tags:** fl.formal-languages, computability, automata-theory, regular-language, grammars

> **Comments:**
> **username_1**: How do you define the *language* accepted by an MDP?  
> **username_2**: You may want to read https://en.wikipedia.org/wiki/Probabilistic_automaton  

---

## 0 answers

