FOLA-demo32.html

Three dimensional alphabet

Construct an NFA for L^r first. We denote n1 & n2 to be the top two rows and m to be the bottom row.

The NFA will be able to verify whether or not m=n1+n2.

Besides q0, we have only one other state

qC: The carry bit from the previous step is 1

The transition function is created by checking all possibilities of the input based on the fact that

m=l+k+c, where c is the carry bit.

> InternalStates:={q0,qC}:
Alphabet:={[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]}:
delta:=table():
delta[(q0,[0,0,0])]:=q0:
delta[(q0,[1,0,1])]:=q0:
delta[(q0,[0,1,1])]:=q0:
delta[(q0,[1,1,0])]:=qC:
delta[(qC,[0,0,1])]:=q0:
delta[(qC,[0,1,0])]:=qC:
delta[(qC,[1,0,0])]:=qC:
delta[(qC,[1,1,1])]:=qC:
InitialState:=q0:
FinalStates:={q0}:
nfa2_10:=mkNFA(InternalStates,Alphabet,op(delta),InitialState,FinalStates):
transitionGraph(nfa2_10);
dfa2_10:=simplifyDFA(minimalDFA(NFA2DFA(nfa2_10)));
transitionGraph(dfa2_10);

Plot_2d

$`:=`(dfa2_10, DFA({_q2, _q1, _q0}, {[1, 1, 1], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]}, TABLE([(_q1, [1, 0, 1]) = _q2, (_q0, [1, 0, 0]) = _q2, (_q1, [0, 0, 1]) = _...$
$`:=`(dfa2_10, DFA({_q2, _q1, _q0}, {[1, 1, 1], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]}, TABLE([(_q1, [1, 0, 1]) = _q2, (_q0, [1, 0, 0]) = _q2, (_q1, [0, 0, 1]) = _...$
$`:=`(dfa2_10, DFA({_q2, _q1, _q0}, {[1, 1, 1], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]}, TABLE([(_q1, [1, 0, 1]) = _q2, (_q0, [1, 0, 0]) = _q2, (_q1, [0, 0, 1]) = _...$
$`:=`(dfa2_10, DFA({_q2, _q1, _q0}, {[1, 1, 1], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]}, TABLE([(_q1, [1, 0, 1]) = _q2, (_q0, [1, 0, 0]) = _q2, (_q1, [0, 0, 1]) = _...$
$`:=`(dfa2_10, DFA({_q2, _q1, _q0}, {[1, 1, 1], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]}, TABLE([(_q1, [1, 0, 1]) = _q2, (_q0, [1, 0, 0]) = _q2, (_q1, [0, 0, 1]) = _...$
$`:=`(dfa2_10, DFA({_q2, _q1, _q0}, {[1, 1, 1], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]}, TABLE([(_q1, [1, 0, 1]) = _q2, (_q0, [1, 0, 0]) = _q2, (_q1, [0, 0, 1]) = _...$
$`:=`(dfa2_10, DFA({_q2, _q1, _q0}, {[1, 1, 1], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]}, TABLE([(_q1, [1, 0, 1]) = _q2, (_q0, [1, 0, 0]) = _q2, (_q1, [0, 0, 1]) = _...$

Plot_2d

> w:=[[0,0,1],[1,0,0],[1,1,0]]:
wR:=w:
for i from 1 to nops(w) do
wR:=subsop(i=w[nops(w)-i+1],wR);
od:
wR;
stringVerificationDFA(dfa2_10,wR);

(7.2.1)

> w:=[[0,0,1],[1,0,1],[1,1,0]]:
wR:=w:
for i from 1 to nops(w) do
wR:=subsop(i=w[nops(w)-i+1],wR);
od:
wR;
stringVerificationDFA(dfa2_10,wR);

(7.2.2)