Example 7.2.1.This LBA recognizes the non context-free language {ww| w__+} over _ = {0,1} using tape alphabet ____{X, Y}.
s00s1Xr
s01s2Xr
s10s10r
s10s3Yl
s11s11r
s21s21r
s21s3Yl
s20s20r
s30s30l
s31s31l
s3Ys3Yl
s3Xs4Xr
s40s5Xr
s41s7Xr
s4Ys9Yr
s50s50r
s51s51r
s5Ys6Yr
s6Ys6Yr
s60s3Yl
s70s70r
s71s71r
s7Ys8Yr
s8Ys8Yr
s81s3Yl
s9Ys9Yr
s90s100r
s91s101r
where e.g.
non-determinism is highlighted in red
Previous slide | Next slide | Back to first slide | View graphic version |