GP Based on CNF: Example 5
/5
1
2
/31
G
= (
N
,
T
,
P
,
S
), where
N
= {
A
,
B
,
C
,
S
},
T
= {
a
,
b
},
P
= {
S
®
A
C
,
C
®
S
B
,
A
®
a
,
B
®
b
,
S
®
c
}
Question:
aacbb
Î
L
(
G
)
?
a
a
c
b
b
S
[
1
, 1]
S
[2, 2]
S
[3, 3]
S
[4, 4]
S
[5,
5
]
={
A
}
={
A
}
={
S
}
={
B
}
={
B
}
S
[
1
, 2]
S
[2, 3]
S
[3, 4]
S
[4,
5
]
=
Æ
=
Æ
={
C
}
=
Æ
S
[
1
, 3]
S
[2, 4]
S
[3,
5
]
=
Æ
={
S
}
=
Æ
S
®
AC
S
[
1
, 4]
S
[2,
5
]
=
Æ
={
C
}
S
[1, 5]
={
S
}
S
Î
S
[
1
,
5
]
YES