<p>The language accepted/recognized by a finite automaton is the set of words that, starting from one of the initial states, arrive at one of the final states.</p>
<p>Sometimes it is also useful to think about the languages of individual states of the automaton. But there are two ways to do that, for any given state X:</p>
<ol>
<li>The set of words that, starting from one of the initial states, arrive at X.</li>
<li>The set of words that, starting from X, arrive at one of the final states.</li>
</ol>
<p>Is there a standard terminology and notation for these two things? Many places I've come across don't seem to clearly distinguish between the two.</p>

CC BY-SA 4.0
2024-10-26T04:42:42.713Z
There is no standard notation for this, but usually for an automaton $A$ we write e.g., $A_p^q$ to denote that we set the initial state to $p$ and the final states to $\{q\}$. But this depends on whether this notation fits well with other notations in the same paper.
Shaull
CC BY-SA 4.0
2024-10-28T12:17:54.043Z
the notation $L_{p,q}$ is also somewhat usual.
Denis
CC BY-SA 4.0
2024-10-29T16:35:53.937Z
A related concept is https://en.wikipedia.org/wiki/Brzozowski_derivative: for any accessible state $q$ in a DFA, the language accepted when starting at $q$ and going to the final states (i.e., point 2 in your question) can be written as $u^{-1} L$ where $L$ is the language of the automaton and $u$ is any word that leads to $q$ when read from the initial state. I don't know of an analogue for point 1 except if the automaton $A$ is codeterministic.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-10-29T16:37:22.297Z
Another related concept: https://en.wikipedia.org/wiki/Semiautomaton. A semiautomaton is an automaton with no initial or final states specified. When you want to consider variants $A^q_p$ of an automaton $A$ like in @Shaull's comment, then maybe it means that you are not interested in the initial and final states of $A$. If that's the case, then $A$ is more accurately called a semiautomaton rather than an automaton.
Antoine Amarilli 'a3nm'
<fl.formal-languages><automata-theory>
In finite automata, what are the names of the languages that arrive at and leave from a given state?
hugomg
# In finite automata, what are the names of the languages that arrive at and leave from a given state?

(Asked by: username_0 on 2024-10-26)

The language accepted/recognized by a finite automaton is the set of words that, starting from one of the initial states, arrive at one of the final states.

Sometimes it is also useful to think about the languages of individual states of the automaton. But there are two ways to do that, for any given state X:

1. The set of words that, starting from one of the initial states, arrive at X.
2. The set of words that, starting from X, arrive at one of the final states.

Is there a standard terminology and notation for these two things? Many places I've come across don't seem to clearly distinguish between the two.

**Tags:** fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: There is no standard notation for this, but usually for an automaton $A$ we write e.g., $A_p^q$ to denote that we set the initial state to $p$ and the final states to $\{q\}$. But this depends on whether this notation fits well with other notations in the same paper.  
> **username_2**: the notation $L_{p,q}$ is also somewhat usual.  
> **username_3**: A related concept is https://en.wikipedia.org/wiki/Brzozowski_derivative: for any accessible state $q$ in a DFA, the language accepted when starting at $q$ and going to the final states (i.e., point 2 in your question) can be written as $u^{-1} L$ where $L$ is the language of the automaton and $u$ is any word that leads to $q$ when read from the initial state. I don't know of an analogue for point 1 except if the automaton $A$ is codeterministic.  
> **username_3**: Another related concept: https://en.wikipedia.org/wiki/Semiautomaton. A semiautomaton is an automaton with no initial or final states specified. When you want to consider variants $A^q_p$ of an automaton $A$ like in @Shaull's comment, then maybe it means that you are not interested in the initial and final states of $A$. If that's the case, then $A$ is more accurately called a semiautomaton rather than an automaton.  

---

## 0 answers

