Slide 1

Report
CONTEXT- FREE
LANGUAGE
Yenni Astuti
Version 1.0.0
n n
{a b : n  0}
R
{ww }
Regular Languages
a *b *
( a  b) *
Context-Free Languages
n n
{a b }
R
{ww }
Regular Languages
Context =
Konteks
Free = Bebas
Context Free
= Bebas
Konteks
Bahasa Bebas Konteks
Grammar Bebas Konteks
(hanya bergantung pada simbol awal)
Context-Free Languages
Context-Free
Grammars
Pushdown
Automata
Context-Free Languages
Context-Free
Grammars
Pushdown
Automata
stack
automaton
Grammar mengekspresikan Bahasa
Contoh 1: Bahasa Indonesia
<kalimat>  <frase_benda> <predikat>
<frase_benda>  <artikula> <predikat>
<predikat>  <kata_kerja>
<artikula>  si
<artikula>  sang
<kata_benda>  kucing
<kata_benda>  tikus
<kata_kerja>  berlari
<kata_kerja>  makan
Penurunan untuk mendapat kalimat “si tikus makan”:
<kalimat>
 <frase_benda> <predikat>
 <frase_benda> <kata_kerja>
 <artikula> <kata_benda> <kata_kerja>
 si <kata_benda> <kata_kerja>
 si tikus <kata_kerja>
 si tikus makan
Penurunan untuk mendapat kalimat “sang kucing berlari”:
<kalimat>
 <frase_benda> <predikat>
 <frase_benda> <kata_kerja>
 <artikula> <kata_benda> <kata_kerja>
 sang <kata_benda> <kata_kerja>
 sang kucing <kata_kerja>
 sang kucing berlari
Bahasa dari grammar <kalimat>  <frase_benda> <predikat>
L = { “si kucing berlari”,
“si tikus berlari”,
“sang kucing berlari”,
“sang tikus berlari”,
“si kucing makan”,
“si tikus makan”,
“sang kucing makan”,
“sang tikus makan” }
NOTASI
Aturan Produksi
<kata_benda>  kucing
<kata_benda>  tikus
Variable
Terminal
Contoh 2.
Grammar:
S  aSb
S
Derivation of sentence:
ab
S  aSb  ab
S  aSb
S
Contoh 2.
Grammar:
S  aSb
S
Derivation of sentence:
aabb
S  aSb  aaSbb  aabb
S  aSb
S
Other derivations:
S  aSb  aaSbb  aaaSbbb  aaabbb
S  aSb  aaSbb  aaaSbbb
 aaaaSbbbb  aaaabbbb
A Convenient Notation
A  aAb
A
artikula  si
artikula  sang
A  aAb | 
artikula  si | sang
Mari Berlatih (1) !!
1. Tuliskan 5 turunan dari aturan produksi berikut:
a. S → aSa | aBa
B → bB | b
b. S → AB
A→B
B→#
c. S → 0S1
S → 01
d. S → abScB | 
B → bB | b
Mari Berlatih (2) !!
Diberikan suatu grammar dengan simbol awal S:
S -> aB
S -> bA
A -> a
A -> aS
A -> BAA
B -> b
B -> bS
B -> ABB
a. Tunjukkan bahwa string ababba termasuk turunan
dari aturan produksi diatas.
b. Buktikan bahwa semua string yang menjadi turunan
aturan produksi tersebut memiliki banyak a dan b
yang sama.
More Notation G  V ,T , S , P 
Grammar
V:
Set of variables
T:
Set of terminal symbols
S:
Start variable
P:
Set of Production rules
Contoh 2.
G : S  aSb
S
Grammar
G  V ,T , S , P 
V  {S}
T  {a, b}
P  {S  aSb, S  }
More Notation
Sentential Form:
A sentence that contains variables and terminals
Contoh:
S  aSb  aaSbb  aaaSbbb  aaabbb
Sentential Forms
sentence
Dituliskan sebagai:
*
S  aaabbb
Daripada:
S  aSb  aaSbb  aaaSbbb  aaabbb
Lebih umum, dituliskan sebagai:
*
w1  wn
Jika
w1  w2  w3    wn
By default:
*
w  w
Contoh 2.
Grammar
S  aSb
S
Derivations
*
S 
*
S  ab
*
S  aabb
*
S  aaabbb
Contoh 2.
Grammar
S  aSb
S
Derivations

S  aaSbb

aaSbb  aaaaaSbbbbb
Contoh 3.
Grammar
G : S  Ab
A  aAb
A
Derivations:
S ⇒Ab ⇒b
S ⇒Ab ⇒aAbb ⇒abb
S ⇒Ab ⇒aAbb ⇒aaAbbb ⇒aabbb
Contoh 3.
S  Ab  aAbb  aaAbbb  aaaAbbbb
 aaaaAbbbbb  aaaabbbbb

S  aaaabbbbb

S  aaaaaabbbbbbb

S a b b
n n
Language of a Grammar
Untuk suatu grammar G
Dengan suatu variabel awal S

L(G )  {w : S  w}
String terminal
Bahasa dari Grammar: S  aSb
S
S  aSb  aaSbb  aaaSbbb
 aaaaSbbbb  aaaabbbb
L  {a b : n  0}
n n
Contoh 3
Untuk suatu grammar G:
S  Ab
A  aAb
A
L(G )  {a b b : n  0}
n n

Mengingat:
S a b b
n n
Mari Berlatih (3) !!
1. Temukan CFG yang dapat menghasilkan Bahasa:
a. L = { an bm | 0 ≤ n ≤ m ≤ 2n}.
b. L = {anbmck : k = n + m }
2. Tuliskan CFG yang menghasilkan Bahasa berikut.
Gunakan alfabet {0,1}.
a. {w|w memiliki sekurangnya tiga 1}
b. {w|w diawali dan diakhiri dengan simbol yang
sama}

similar documents