Language of a machine

From CS2800 wiki
(Redirected from L(M))

The language of an automaton [math]M [/math], written [math]\href{/cs2800/wiki/index.php/L(M)}{L(M)} [/math] is the set of strings that [math]M [/math] accepts.

The exact definition of [math]L(M) [/math] depends on the type of automaton.


If [math]M [/math] is a DFA, informally [math]M [/math] accepts [math]x [/math] if [math]M [/math] ends in an accepting state after processing [math]x [/math]. This is formalized using the extended transition function:

Definition: L(M) for DFA
If [math]M [/math] is a DFA, then the language of M (written L(M)) is given by [math]L(M) := \{x \in \href{/cs2800/wiki/index.php?title=%5CSigma%5E*&action=edit&redlink=1}{\Sigma^*} \mid \href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}_M}(\href{/cs2800/wiki/index.php?title=Q0&action=edit&redlink=1}{q_{0M}},x) \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php?title=A&action=edit&redlink=1}{A}\} [/math].


Language of an NFA