Skip to content

Instantly share code, notes, and snippets.

@Capital-EX
Last active November 23, 2019 03:25
Show Gist options
  • Save Capital-EX/78ae980e39674e45b6d70582f02009c1 to your computer and use it in GitHub Desktop.
Save Capital-EX/78ae980e39674e45b6d70582f02009c1 to your computer and use it in GitHub Desktop.
name: palindrome
source code: |
# Accepts palindromes made of the symbols 'a' and 'b'
input: 'abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcba' # try a, ab, bb, babab
blank: ' '
start state: start
synonyms:
accept: {R: accept}
reject: {R: reject}
# A palindrome is either the empty string, a single symbol,
# or a (shorter) palindrome with the same symbol added to both ends.
table:
start:
a: {write: ' ', R: haveA}
b: {write: ' ', R: haveB}
c: {write: ' ', R: haveC}
d: {write: ' ', R: haveD}
e: {write: ' ', R: haveE}
f: {write: ' ', R: haveF}
g: {write: ' ', R: haveG}
h: {write: ' ', R: haveH}
i: {write: ' ', R: haveI}
j: {write: ' ', R: haveJ}
k: {write: ' ', R: haveK}
l: {write: ' ', R: haveL}
m: {write: ' ', R: haveM}
n: {write: ' ', R: haveN}
o: {write: ' ', R: haveO}
p: {write: ' ', R: haveP}
q: {write: ' ', R: haveQ}
r: {write: ' ', R: haveR}
s: {write: ' ', R: haveS}
t: {write: ' ', R: haveT}
u: {write: ' ', R: haveU}
v: {write: ' ', R: haveV}
w: {write: ' ', R: haveW}
x: {write: ' ', R: haveX}
y: {write: ' ', R: haveY}
z: {write: ' ', R: haveZ}
' ': accept
haveA:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchA}
haveB:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchB}
haveC:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchC}
haveD:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchD}
haveE:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchE}
haveF:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchF}
haveG:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchG}
haveH:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchH}
haveI:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchI}
haveJ:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchJ}
haveK:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchK}
haveL:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchL}
haveM:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchM}
haveN:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchN}
haveO:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchO}
haveP:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchP}
haveQ:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchQ}
haveR:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchR}
haveS:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchS}
haveT:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchT}
haveU:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchU}
haveV:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchV}
haveW:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchW}
haveX:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchX}
haveY:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchY}
haveZ:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: R
' ': {L: matchZ}
matchA:
a: {write: ' ', L: back}
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchB:
b: {write: ' ', L: back}
a: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchC:
c: {write: ' ', L: back}
a: reject
b: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchD:
d: {write: ' ', L: back}
a: reject
b: reject
c: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchE:
e: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchF:
f: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchG:
g: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchH:
h: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchI:
i: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchJ:
j: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchK:
k: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchL:
l: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchM:
m: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchN:
n: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchO:
o: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchP:
p: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchQ:
q: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchR:
r: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchS:
s: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchT:
t: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
u: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchU:
u: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
v: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchV:
v: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
w: reject
x: reject
y: reject
z: reject
' ': accept
matchW:
w: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
x: reject
y: reject
z: reject
' ': accept
matchX:
x: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
y: reject
z: reject
' ': accept
matchY:
y: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
z: reject
' ': accept
matchZ:
z: {write: ' ', L: back}
a: reject
b: reject
c: reject
d: reject
e: reject
f: reject
g: reject
h: reject
i: reject
j: reject
k: reject
l: reject
m: reject
n: reject
o: reject
p: reject
q: reject
r: reject
s: reject
t: reject
u: reject
v: reject
w: reject
x: reject
y: reject
' ': accept
back:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]: L
' ': {R: start}
accept:
reject:
# Exercise:
# • Modify the machine to include 'c' in the symbol alphabet,
# so it also works for strings like 'cabbac'.
positions:
start: {x: 399.13, y: 333.53}
haveA: {x: 39.1, y: 76.15}
haveB: {x: 107.07, y: 79.8}
haveC: {x: 178.43, y: 81.37}
haveD: {x: 245.02, y: 81.37}
haveE: {x: 313.4, y: 83.52}
haveF: {x: 389.01, y: 79.5}
haveG: {x: 455.89, y: 81.12}
haveH: {x: 524.13, y: 83.46}
haveI: {x: 590.89, y: 86.79}
haveJ: {x: 653.64, y: 88.16}
haveK: {x: 724.7, y: 90.85}
haveL: {x: 37.56, y: 261.97}
haveM: {x: 105.4, y: 264.85}
haveN: {x: 177.29, y: 265.22}
haveO: {x: 240.79, y: 269.42}
haveP: {x: 300.39, y: 272.88}
haveQ: {x: 516.33, y: 257.75}
haveR: {x: 582.43, y: 255.72}
haveS: {x: 639.5, y: 263.83}
haveT: {x: 703.22, y: 272.11}
haveU: {x: 46.77, y: 425.13}
haveV: {x: 109.97, y: 436.17}
haveW: {x: 184.98, y: 431.05}
haveX: {x: 261.72, y: 423.02}
haveY: {x: 489.57, y: 423.75}
haveZ: {x: 557.66, y: 433.25}
matchA: {x: 41.29, y: 160.13}
matchB: {x: 107.8, y: 163.05}
matchC: {x: 178.71, y: 166.44}
matchD: {x: 248.11, y: 168.3}
matchE: {x: 309.46, y: 171.7}
matchF: {x: 382.31, y: 169.22}
matchG: {x: 450.5, y: 173.94}
matchH: {x: 512.06, y: 177.17}
matchI: {x: 572.7, y: 175.51}
matchJ: {x: 626.42, y: 173.59}
matchK: {x: 697.75, y: 177.14}
matchL: {x: 41.34, y: 336.92}
matchM: {x: 107.07, y: 342.05}
matchN: {x: 174.67, y: 346.91}
matchO: {x: 237.31, y: 347.04}
matchP: {x: 297.82, y: 338.45}
matchQ: {x: 519.26, y: 334.86}
matchR: {x: 576.49, y: 341.4}
matchS: {x: 637.1, y: 346.83}
matchT: {x: 693.03, y: 346.27}
matchU: {x: 49.67, y: 474.52}
matchV: {x: 120.09, y: 480}
matchW: {x: 192.61, y: 478.35}
matchX: {x: 266.57, y: 480}
matchY: {x: 529.28, y: 480}
matchZ: {x: 599.41, y: 480}
back: {x: 402.19, y: 413.62}
accept: {x: 397.08, y: 235.44}
reject: {x: 405.84, y: 477.87}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment