4. Nondeterminism

DFA as a theoretical model for programming

$-$ unusual / visual, different from conventional programming languages $+$ major concepts of imperative programming (e.g. sequences, branching, loops) can be simulated $+$ elegant, simple to use (visual), has a developed theory $+$ all pattern matching can be described $-$ limited expressive power (constant amount of memory)

Combining two automata

High-level languages typically implement things such as method calling and modularity, in this section we try to determine if we can do the same with finite automata.

Design an automaton $A$ such that $L(A)$ consits of all the strings of $a$s and $b$s that have either two consecutive $a$s or two consecutive $b$s.

Since we already have the ‘methods’ to solve the problem for $aa$s and $bb$s, we could design a ‘main program’ that would just call the given methods. One possible solution would be to combine the initial states.

$$\begin{array}{rl}L(A_3)& =\text{all the words having two consecutive }a\text{s}\\ L(A_3^{\prime })& =\text{all the words having two consecutive }b\text{s}\end{array}$$

Automaton $A$ such that $L(A)=L(A_3)\cup L(A_3^{\prime })$

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; r1, r2;
	node[shape=circle];
	init->s
	
	s->s [label=a]
	s->s [label=b]
	
	s->q2 [label=b]
	q2->s [label=a]
	q2->r2 [label=b]
	r2->r2 [label=a]
	r2->r2 [label=b]
	
	s->q1 [label=a]
	q1->s [label=b]
	q1->r1 [label=a]
	r1->r1 [label=b]
	r1->r1 [label=a]
}

Observe that the state transition diagram on the previous slide no longer represents a DFA:

• there is more than one $a$-arrow leaving state $s$
• there is more than one $b$-arrow leaving state $s$

We say that this automaton is nondeterministic, this is because given a state $s$ and reading $a$ from the input tape, the device has a choice to either move to state $q_1$ or $s$. In order words, the next state is not determined by the previous state and the symbol read.