Teori Bahasa & Otomata - Danang Junaedi
IF-UTAMA
1
Language Is Cool Chomsky Normal Form (CNF) & Greibach Normal Form (GNF)
• Language: A protocol for the transmission of concepts and intentions between humans – Documentation is not available – Documentation does not really work – Learned through exposure and use • Significant amount of internal structure, redundancy, and consistency • Who makes language? – Kids. • Adults coin words here and there, but when they’re forced to invent a common language to get things done, it’s called a Pidgin, and it’s terrible • The kids hear it, and invent a Creole – a merged language of significantly greater accuracy and depth • Children make languages • Adults make “working” languages • Programmers make barely working languages
Dosen Pembina Danang Junaedi
IF-UTAMA
Normal Forms
2
The Chomsky Hierarchy Type
• Normal forms are special types of context-free languages. • Having more restricted (but still powerful) grammar forms make important algorithms efficient. • Two widely-known forms: Chomsky Normal and Greibach Normal
Language
Grammar
Automaton
0
Partially Computable
Unrestricted
DTM - NTM
1
Context Sensitive
Context Sensitive
Linearly Bounded Automaton
2
Context Free
Context Free
NPDA
3
Regular
right regular, left regular
DFA, NFA
You don’t have to know this
Type 3 ⊂ Type 2 ⊂ Type 1 ⊂ Type 0
IF-UTAMA
IF - UTAMA
3
IF-UTAMA
4
1
Teori Bahasa & Otomata - Danang Junaedi
Chomsky Normal Form (CNF)
The Chomsky Hierarchy Partially Computable Languages
{M, H(<M>)}
Computable Languages
{an bn cn , n ≥ 0}
A CFG is in Chomsky Normal Form if all its productions are of the form: A → BC or A→a where A, B, C ∈ V and a ∈ T. Also, S → ε may be one of the productions.
Context Free Languages {an bn , n ≥ 0} Regular Languages {am bn , m,n ≥ 0}
IF-UTAMA
5
Examples of CNF Example 1:
Example 2:
IF - UTAMA
6
Examples of CNF
S → AS S →a A → SA A→b
S → AB A → BC | CC | a B → CB | b C→c S → AB | BC | AC | ε A → BC | a B → AC | b C → AB | c
IF-UTAMA
IF-UTAMA
S → AS S → AAS A → SA A → aa Not Chomsky Normal Form
Chomsky Normal Form
7
IF-UTAMA
8
2
Teori Bahasa & Otomata - Danang Junaedi
Algorithm for Converting to CNF
CNF
• Step (1) Eliminate ε-productions and unit productions • Step (2) For remaining production α → β not form A → BC nor of form A → a, replace occurrences of terminals a, b, c, … in β with new nonterminal representatives Ca, Cb, Cc, … and then add new productions Ca → a Cb → b Cc → c … • Step (3) If right-hand side of any production contains three or more nonterminals, then decompose this production into a series of productions the right-hand sides of which consist of exactly two nonterminals.
Is that all Context Free Grammars can be expressed in Chomsky Normal Form? Consider the following simple grammar: A → cA | a B → ABC | b C→c
How to convert this grammar to CNF?
IF-UTAMA
9
Power of Chomsky Normal
IF - UTAMA
10
Conversion into CNF
• Every CFG can be rewritten in Chomsky Normal Form • Step 1: For any production rule with more than one terminal on the right, substitute all with variables. • Step 2: Substitute more variables in order to make the variable strings shorter.
IF-UTAMA
IF-UTAMA
Step 1: Convert every production into either: A→ B1B2…Bn or A→ a e.g. A → bCDeF becomes: A → BCDEF B→b E→e Step 2: Convert production of the form A→ B1B2…Bn into A → C1C2 : e.g. A → BCDEF becomes: A → BX X → CY Y → DZ Z → EF 11
IF-UTAMA
12
3
Teori Bahasa & Otomata - Danang Junaedi
Example: Convert to CNF Original: S -> ABa A -> aab B -> Ac
Step 1: S -> ABBa A -> BaBaBb B -> ABc Ba -> a Bb -> b Bc -> c
Class Discussion
Step 2:
Convert the following CFG into Chomsky Normal Form: S→ε S → ABBA B → bCb A→a C→c
S -> AD1 D1 ->BBa A -> BaD2 D2 ->BaBb B -> ABc Ba -> a Bb -> b Bc -> c
IF-UTAMA
13
Greibach Normal Form (GNF)
Example 1: S → aABC A → aA | a B → bB | b C → cC | c Example 2: S → bAB | ε A → aBAA | aAAB | a B → bABB | bBBA | b
Advantages: • Every derivation of a string s contains |s| rule applications. • Greibach normal form grammars can easily be converted to pushdown automata with no ε-transitions. This is useful because such PDAs are guaranteed to halt.
IF - UTAMA
14
Examples of GNF
A CFG is in Greibach Normal Form if all its productions are of the form: A → aα where A ∈ V, a ∈ T and α ∈ V*. Also, S → ε may be one of the productions.
IF-UTAMA
IF-UTAMA
15
IF-UTAMA
16
4
Teori Bahasa & Otomata - Danang Junaedi
Conversion Algorithm
GNF
• Step (1) Find equivalent grammar G´ in CNF • Step (2) Order nonterminals of G´ from X1 to Xn. • Step (3) Work upward through nonterminals of G´, making replacements so as to ensure that all ultimately ascending. • Step (4) Work downward through nonterminals, making replacements so as to ensure that all productions ultimately in GNF, i.e., of form X→aα, where X nonterminal, a is a terminal, and α (possibly empty) string of non-terminals.
IF-UTAMA
Is that all Context Free Grammars can be expressed in Greibach Normal Form? Transformation can be done by a combination of substitution and removal of left recursion.
17
Removal of Left Recursion
1. Pisahkan aturan produksi yang rekursif kiri dan tidak rekursif kiri – Aturan produksi yang rekursif kiri X → Xβ1 | Xβ2 | … | Xβn Kita dapatkan simbol β1, β2,…,βn – Aturan produksi yang tidak rekursif kiri X → α1 | α2 | … | αn Kita dapatkan simbol α1, α2,…,αn 2. Lakukan penggantian aturan produksi yang rekursif kiri menjadi X → α1 | α2 | … | αn X → α1Z | α2Z | … | αnZ Z → β1 | β2 | … | βn Z → β1Z | β2Z | … | βnZ dimana simbol Z adalah variabel non terminal baru yang kita buat sesuai banyaknya variablel pada aturan produksi yang rekursif kiri
This is called a left recursion.
IF-UTAMA
IF - UTAMA
18
Tahapan Penghilangan Rekursif Kiri[5]
We want to remove all the productions in the form of: A → Aα
Replace: X → α1 | α2 | … | αn X → Xβ1 | Xβ2 | … | Xβ n by: X → α1 | α2 | … | αn X → α1Z | α2Z | … | αnZ Z → β1 | β 2 | … | βn Z → β 1Z | β 2Z | … | β nZ
IF-UTAMA
where X ∈ V αi, βi ∈ (V ∪T)* such that αi does not start with X
19
IF-UTAMA
20
5
Teori Bahasa & Otomata - Danang Junaedi
Studi Kasus [5]
Contoh Penghilangan Rekursif Kiri
Hilangkan rekursif kiri dari aturan-aturan produksi berikut ini:
Hilangkan rekursif kiri untuk aturan produksi berikut: E E+T ET Solusi: 1. Pisahkan aturan produksi yang rekursif kiri dan tidak rekursif kiri – Aturan produksi yang rekursif kiri E E+T Kita dapatkan simbol α1 +T – Aturan produksi yang tidak rekursif kiri ET Kita dapatkan simbol β 1 T 2. Lakukan penggantian aturan produksi yang rekursif kiri menjadi E→T Aturan produksi baru yang E → TZ dihasilkan dari pengilangan Z → +T aturan produksi yang rekursif kiri Z → +TZ IF-UTAMA
1. S Sab | aSc | dd | ff | Sbd 2. S Sab | Sb | cA AAa | a | bd 3. S Sa | aAc | c | ε A Ab | ba
21
Pembentukan GNF (1) [5] 1. Aturan Produksi telah dalam bentuk CNF dan tidak menghasilkan ε 2. Tentukan urutan simbol-simbol variabel yang ada dalam tata bahasa. Misalkan terdapat “n” variabel non terminal dengan urutan α1, α2, …,αn 3. Berdasarkan urutan simbol tersebut seluruh aturan produksi dapat ditulis dalam bentuk αh αi λ (dimana h ≤ i) a. Jika h < I, aturan produksi sudah benar b. Jika h>I, lakukan subtitusi berulang (ganti αI dengan variabel yang ada di ruas kanannya) sampai diperoleh bentuk αh αp λ (dimana h ≤ p) • Jika h
IF - UTAMA
IF-UTAMA
22
Pembentukan GNF dengan Subtitusi(2) [5] Jika step 2 dan 3 sudah dikerjakan akan menghasilkan aturan produksi dengan urutan yang benar yaitu αh αi λ (h
IF-UTAMA
CDD
24
6
Teori Bahasa & Otomata - Danang Junaedi
Pembentukan GNF dengan Subtitusi(3) [5]
Pembentukan GNF dengan Subtitusi(4) [5]
Solusi: 2. Tentukan urutan simbol-simbol variabel yang ada dalam tata bahasa. Misalkan terdapat “n” variabel non terminal dengan urutan α1, α2, …,αn Vn : { S A B C D }
↓
↓
↓
↓
↓
α1 α 2 α 3 α 4 α 5
3.
Aturan produksi menjadi α2 a | d α3b α1 α4α2 α4 α5α5 α5 α2α3 Cek apakah berdasarkan urutan simbol tersebut seluruh aturan produksi dalam bentuk αh αi λ dimana (h≤i) α1 α4α2 (sudah benar karena 1<4) α4 α5α5 (sudah benar karena 4<5) α5 α2α3 (salah karena 5>2) =>subtitusi berulang (ganti α2 dengan variabel yang ada di ruas kanannya) sampai diperoleh bentuk αh αp λ (dimana h ≤ p) IF-UTAMA
α5 α2α3 menjadi α5 aα3 | dα3 sehingga menghasilkan aturan produksi dengan urutan yang benar yaitu: α2 a | d α3b α1 α4α2 α4 α5α5 α5 aα3 | dα3 4. Subtitusi mundur α5 aα3 | dα3 α4 aα3α5 | dα3α5 α1 aα3α5α2 | dα3α5 α2 α1 α 2 α 3 α 4 α 5 Ubah variabel α1,…, αn ke variabel semula ↓ S
Menjadi SaBDA | dBDA C aBD | dBD
25
Studi Kasus
↓ C
↓ D
Bb
IF-UTAMA
1.
S → c | Sa | SbA A → c S AA |d A SS | b A ABC B CA | b S aSb | ab | SS
2.
3.
C AB | a 4.
5.
IF-UTAMA
IF - UTAMA
↓ B
26
References
Ubah aturan produksi berikut ini ke dalam bentuk normal greibach: 1. 2. 3. 4.
A a | d D aB | dB
↓ A
27
-,”Simplification of CFG”, http://www.geocities. com/ parouyr_sevak/03L11.ppt,Tanggal Akses 16 Mei 2009 Dr. William Thacker’s ,”Context-Free Grammars: Chapter 11 Normal Formal ”,http://cba.winthrop. edu/thackerw/CSCI371/powerpoint%20slides/Ch11bNormalFor ms.ppt, Tanggal Akses 16 Mei 2009 -,” Context-Free Languages and Pushdown-Stack Automata : An Intermediate-Strength Model of Computation”, http://home.manhattan.edu/~gregory.taylor/thcomp/slides/chapt er10.ppt, Tanggal Akses 16 Mei 2009 -,”Chomsky Hierarchy Language Operations and Properties”, http://wwwcs.ccny.cuny.edu/~vmitsou/extra/Chomskyhier.ppt, Tanggal Akses 16 Mei 2009 Firrar Utdirartatmo, “Teori Bahasa dan Otomata”, Graha Ilmu, Yogyakarta, 2005 IF-UTAMA
28
7
