FOLA-demo30.html

L={w:the bottm row is three times the top row}

Construct an NFA for L^r first. We denote n to be the top row and m to be the bottom row.

m=3*n means adding n to n', which is n after shifting one position to the left.

Besides q0, we have three other states

q01: The previous symbol in n is 0, and the carry bit is 1

q10: The previous symbol in n is 1, and the carry bit is 0

q11: The previous symbol in n is 1, and the carry bit is 1

If the previous symbol is 0 and the carry bit is also 0, the intermediate result has the bottom row is three times the top row.

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

a p

a+p+c=b, where c is the carry bit.

> InternalStates:={q0,q01,q10,q11}:
Alphabet:={[0,0],[0,1],[1,0],[1,1]}:
delta:=table():
delta[(q0,[0,0])]:=q0:
delta[(q0,[1,1])]:=q10:
delta[(q01,[0,1])]:=q0:
delta[(q01,[1,0])]:=q11:
delta[(q10,[0,1])]:=q0:
delta[(q10,[1,0])]:=q11:
delta[(q11,[0,0])]:=q01:
delta[(q11,[1,1])]:=q11:
InitialState:=q0:
FinalStates:={q0}:
nfa2_9b:=mkNFA(InternalStates,Alphabet,op(delta),InitialState,FinalStates):
transitionGraph(nfa2_9b);
dfa2_9b:=simplifyDFA(minimalDFA(NFA2DFA(nfa2_9b)));
transitionGraph(dfa2_9b);

Plot_2d

$`:=`(dfa2_9b, DFA({_q_1, _q_2, _q_3, _q_4}, {[0, 1], [1, 1], [0, 0], [1, 0]}, TABLE([(_q_4, [0, 1]) = _q_2, (_q_1, [1, 0]) = _q_2, (_q_2, [0, 0]) = _q_2, (_q_4, [1, 0]) = _q_2, (_q_1, [0, 1]) = _q_2, ...$
$`:=`(dfa2_9b, DFA({_q_1, _q_2, _q_3, _q_4}, {[0, 1], [1, 1], [0, 0], [1, 0]}, TABLE([(_q_4, [0, 1]) = _q_2, (_q_1, [1, 0]) = _q_2, (_q_2, [0, 0]) = _q_2, (_q_4, [1, 0]) = _q_2, (_q_1, [0, 1]) = _q_2, ...$
$`:=`(dfa2_9b, DFA({_q_1, _q_2, _q_3, _q_4}, {[0, 1], [1, 1], [0, 0], [1, 0]}, TABLE([(_q_4, [0, 1]) = _q_2, (_q_1, [1, 0]) = _q_2, (_q_2, [0, 0]) = _q_2, (_q_4, [1, 0]) = _q_2, (_q_1, [0, 1]) = _q_2, ...$
$`:=`(dfa2_9b, DFA({_q_1, _q_2, _q_3, _q_4}, {[0, 1], [1, 1], [0, 0], [1, 0]}, TABLE([(_q_4, [0, 1]) = _q_2, (_q_1, [1, 0]) = _q_2, (_q_2, [0, 0]) = _q_2, (_q_4, [1, 0]) = _q_2, (_q_1, [0, 1]) = _q_2, ...$
$`:=`(dfa2_9b, DFA({_q_1, _q_2, _q_3, _q_4}, {[0, 1], [1, 1], [0, 0], [1, 0]}, TABLE([(_q_4, [0, 1]) = _q_2, (_q_1, [1, 0]) = _q_2, (_q_2, [0, 0]) = _q_2, (_q_4, [1, 0]) = _q_2, (_q_1, [0, 1]) = _q_2, ...$

Plot_2d

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

(7.1.2.1)

> w:=[[0,0],[0,1],[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_9b,wR);

(7.1.2.2)