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/11 17:16] vkuncak |
finite_state_machine [2009/04/28 20:05] vkuncak |
||
|---|---|---|---|
| Line 43: | Line 43: | ||
| **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 \}$. | ||
| + | |||
| + | 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$. | 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$. | ||