CIT 594 Simulating an Unrestricted Grammar with a Modified Post Correspondence Problem
Spring 2012, David Matuszek

S → aABb | Bbb
Bb → C
AC → aac

w = aaac      S ⇒ aABb ⇒ aAC ⇒ aaac

start 1
FS⇒
F
                       
copy 2
a
a
3
b
b
4
c
c
5
A
A
6
B
B
7
C
C
8
S
S
end 9
E
⇒aaacE
                       
productions 10
aABb
S
11
Bbb
S
12
C
Bb
13
aaC
AC
    14
   

1 10 14 2 5 12 14 2 13 9
FS⇒
F
aABb
S
a
a
A
A
C
Bb
a
a
aaC
AC
E
⇒aaacE