Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
finite_state_machine [2008/09/09 21:31] vkuncak |
finite_state_machine [2009/04/28 20:05] vkuncak |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| A finite state machine is a way of defining a language (see [[Strings and languages]]). We give a string to the machine, which examines the string one character by one, and at the end decides whether the string is the language or not. | A finite state machine is a way of defining a language (see [[Strings and languages]]). We give a string to the machine, which examines the string one character by one, and at the end decides whether the string is the language or not. | ||
| - | A non-deterministic 'finite state machine' (also called 'finite automaton') is a five-tuple $(\Sigma,Q,\Delta,q_0,F)$ where | + | A **non-deterministic finite state machine** (also called 'finite automaton') is a five-tuple $(\Sigma,Q,\Delta,q_0,F)$ where |
| * $\Sigma$ is a finite alphabet | * $\Sigma$ is a finite alphabet | ||
| * $Q$ is a **finite** set of states | * $Q$ is a **finite** set of states | ||
| Line 16: | Line 16: | ||
| * we put a symbol $>$ in front of the initial state $q_0$ | * we put a symbol $>$ in front of the initial state $q_0$ | ||
| - | Example finite state machine: | + | **Example** finite state machine: |
| \begin{eqnarray*} | \begin{eqnarray*} | ||
| \Sigma &=& \{b,a,r\} \\ | \Sigma &=& \{b,a,r\} \\ | ||
| Line 35: | Line 35: | ||
| Formally, we define $\Delta_{run}(S,a_1 \ldots a_n)$ as the set of all states $q_{n+1}$ such that there exists an execution with given $a_1,\ldots,a_n$, with $q_1 \in S$, and witn some $q_2,\ldots,q_n \in Q$. | Formally, we define $\Delta_{run}(S,a_1 \ldots a_n)$ as the set of all states $q_{n+1}$ such that there exists an execution with given $a_1,\ldots,a_n$, with $q_1 \in S$, and witn some $q_2,\ldots,q_n \in Q$. | ||
| - | An accepting execution is an execution where $q_1 = q_0$ and $q_{n+1} \in F$. We say that $A$ **accepts** the string $a_1\ldots a_n$ iff there exists an accepting execution of $A$ on $a_1,\ldots,a_n$. We define the **language of the automaton**, denoted $L(A)$, as the set of all strings that $A$ accepts. | + | An **accepting execution** is an execution where $q_1 = q_0$ and $q_{n+1} \in F$. We say that $A$ **accepts** the string $a_1\ldots a_n$ iff there exists an accepting execution of $A$ on $a_1,\ldots,a_n$. We define the **language of the automaton**, denoted $L(A)$, as the set of all strings that $A$ accepts. |
| We then have | We then have | ||
| Line 42: | Line 42: | ||
| \end{equation*} | \end{equation*} | ||
| - | Example: the example automaton above accepts the language $L = \{a, bara, barbara, barbarbara, \ldots \}$, which we can denote by $\{ (bar)^n a \mid n \geq 0 \}$. | + | **Example:** the example automaton above accepts the language $L = \{a, bara, barbara, barbarbara, \ldots \}$, which we can denote by $\{ (bar)^n a \mid n \geq 0 \}$. |
| - | A state machine is called **deterministic** iff for every pair $(q_1,a) \in Q \times \Sigma$ there exists exactly one $q_2 \in Q$ such that $(q_1,a,q_2) \in \Delta$. | + | What is the automaton accepting strings of the form $p\ barbara\ q$ where $p,q$ are arbitrary strings? |
| + | A state machine is called **deterministic** iff for every pair $(q_1,a) \in Q \times \Sigma$ there exists exactly one $q_2 \in Q$ such that $(q_1,a,q_2) \in \Delta$. | ||