Teori Bahasa dan Automata - Konversi DFA ke CFG

Tatabahasa Linier

G = ( V, T, P, S )
Dimana V = Variabel yang digunakan
              T = Input yang ada

1. Konversi FSA -> CFG
    Aturan pengubahan:
    - setiap transisi status d(A, a) = B diubah menjadi aturan produksi A -> aB
    - Setiap final state P diubah bentuknya menjadi aturan produksi P -> epsilon
DFA

Tatabahasa Linier untuk FSA diatas adalah
G = ( {S, S1, S2, S3} , {a, b}, P, S )
dengan aturan produksi P:
S -> S1
S1 -> aS2
S2 -> bS3
S3 -> epsilon

NFA

Tatabahasa Linier untuk FSA diatas adalah
G = ( {L1,L2,L3} , {a,b,c}, P, S )
dengan aturan produksi P:
L1 -> aL2 | bL3
L2 -> aL3 | bL1 | bL2
L3 -> aL3 | bL3 | cL1 | bL2 | epsilon

2. Konversi RE ke CFG
Aturan:

Contoh: Diketahui RE = ( 01* | a )* b ( 01 | 10 )? b
CFG =
***PERMISALAN: A = (01* | a)* ; B = b; C = (01 | 10)? ; D = b
      E = 01* | a ; F = 1* ; G = 01 | 10;
***HINT = R? -> R + epsilon

S -> A B C D
A -> EA | epsilon
E -> 0F | a
F -> 1F | epsilon
B -> b
C -> G + epsilon
G -> 01 | 10
D -> b

atau B dan D dihilangkan, menjadi
S -> A b C b (b tidak dimisalkan lagi)