Christine Sotanto

Ditentukan 2 buah titik, dimana salah satu titik merupakan titik pusat dari sebuah lingkaran dan mempunyai jari – jari. Bagaimana memastikan titik yang lain apakah titik tersebut berada di dalam lingkaran, atau berada pada garis lingkaran, atau berada diluar lingkaran ?

Jawab :

Persamaan lingkaran dengan pusat di A (a, b) dan berjari-jari r, yaitu :

Jika diketahui suatu titik B (x1 , y1), maka untuk memastikan apakah titik B berada di dalam lingkaran, atau berada pada garis lingkaran, atau berada diluar lingkaran dapat dibuat pseudocode seperti berikut :

Pseudocode :

Input x1 , y1
Input a , b
Input r

if (x1-a)^2 + (y1-b)^2 < r^2
print “Titik berada didalam lingkaran”
else if (x1-a)^2 + (y1-b)^2 = r^2
print “Titik berada pada garis lingkaran”
else
print “Titik berada diluar lingkaran”

 

Code generator :

01. mov x1,R0
02. mov a, R1
03. sub R1,R0
04. mul R0,R0
05. mov y1, R2
06. mov b, R3
07. sub R3,R2
08. mul R2,R2
09. add R2,R0
10. mov r,R4
11. mul R4,R4
12. lt R4,R0
13. jmpf R0,(16)
14. prt “Titik berada didalam lingkaran”
15. jmp ,(21)
16. eq R4,R0
17. jmpf R0,(20)
18. prt “Titik berada pada garis lingkaran”
19. jmp ,(21)
20. prt “Titik berada diluar lingkarang”
21. …

 

http://binus.ac.id

1. S -> S + A | S – A | A + S | A – S | B * A

B -> aB | B(a + B) | B * a | a(a + B) | b

A -> a

Jawab :

S-> AS’’ | B*AS’

S’ -> +AS’ | -AS’ | ε

S’’ -> +SS’ | -SS’

B -> aB’’ | bB’

B’ -> (a+B)B’ | *aB’ | ε

B’’ -> BB’ | (a+B)B’

A -> a

First (S)	->	{a,b }
First (S’)	->	{ +,-, ε }
First (S’’)	->	{+,- }
First (B)	->	{a,b }
First (B’)	->	{ (,*,ε }
First (B’’)	->	{ a,b,(}
First (A)	->	{a }

Follow (S)	->	{ $}
Follow (S’)	->	{ $}
Follow (V)	->	{:}
Follow (V’)	->	{:}
Follow (E)	->	{ then,$,),]}
Follow (E’)	->	{ then,$,),]}
Follow (T)	->	{ +,-}
Follow (T’)	->	{ +,- }
Follow (F)	->	{ *,/ }

	a	b	+	–	*	(	$
S	S-> AS’’| B*AS’	S->B*AS’
S’			S’ -> +AS’	S’ -> -AS’			S’ -> ε
S’’			S’’ -> +SS’	S’’ -> -SS’
B	B -> aB’’	B -> bB’’
B’	B’-> ε				B’->*aB’| ε	B’ -> (a+B)B’ | ε
B’’	B’’ -> BB’	B’’ -> BB’				B’’->(a+B)B’
A	A -> a

2.      2. S -> if E then S | if E then S else S | V := E

V -> id | id [E]

E -> E + T | E – T | T

T -> T * F | T / F | F

F -> V | (E) | const

S -> if E then S S’ | V := E

S’ -> ε | else S

V -> idV’

V’ -> ε | [E]

E -> TE’

E’ -> +TE’ | -TE’ | ε

T -> FT’

T ‘-> *FT’ | /FT’ | ε

F -> V | (E) | const

First (S)	->	{if,id }
First (S’)	->	{ ε,else }
First (V)	->	{ id}
First (V’)	->	{ ε ,[}
First (E)	->	{ id,(,const}
First (E’)	->	{ +,-, ε }
First (T)	->	{ id,(,const}
First (T’)	->	{ *,/, ε }
First (F)	->	{ id,(,const}

Follow (S)	->	{ $}
Follow (S’)	->	{ $}
Follow (V)	->	{:}
Follow (V’)	->	{:}
Follow (E)	->	{ then,$,),]}
Follow (E’)	->	{ then,$,),]}
Follow (T)	->	{ +,-}
Follow (T’)	->	{ +,- }
Follow (F)	->	{ *,/ }

 

 

 

 

 

 

3.S-> a = A

A -> aA’ | bA’

A’ -> +AA’ | ε

First (S)                 : { a }

First (A)                 : { a, b }

First (A’)               : { +, ε }

Follow (S)            : { $ }

Follow (A)           : { $, + }

Follow (A’)          : { $, + }

	a	b	+	$
S	S-> a = A
A	A -> aA’	A -> bA’
A’			A’ -> +AA’ | ε	A’ -> ε

4.Diketahui grammar:

be -> bt be^’

be’ -> or bt be’

be’ -> ε

bt-> bf bt’

bt -> and bf bt’

bt’-> ε

bf -> not bf

bf -> (be)

bf -> true

bf -> false

Inputan: not (true or false) and true and true and false not (false) true

First (be)              = {not , ( , true , false}

First (be’)            = {or , ε}

First (bt)               = {not , ( , true , false}

First (bt’)             = {and , ε}

First (bf)               = {not , ( , true , false}

Follow (be)         = {$ , )}

Follow (be’)        = {$ , )}

Follow (bt)          = {or , $ , )}

Follow (bt’)         = {or , $ , )}

Follow (bf)          = {or, $, ) , and}

	or	not	(	)	true	false	and	$
be		be->bt be’	be->bt be’		be->bt be’	be->bt be’
be’	be’->or bt be’			be’->ε				be’->ε
bt		bt->bf bt’	bt->bf bt’			bt->bf bt’	bt->bf bt’
bt’	bt’->ε			bt’->ε			bt’-> and bf bt’	bt’->ε
bf		bf->not bf	bf-> (be)		bf->true	bf->false

No	Stack	Input	Output
1.	be $	not (true or false) and true and true and false not (false) true	be -> bt be’
2.	bt be’ $	not (true or false) and true and true and false not (false) true	bt -> bf bt’
3.	bf bt’ be’ $	not (true or false) and true and true and false not (false) true	bf -> not bf
4.	not bf bt’ be’ $	not (true or false) and true and true and false not (false) true	pop not
5.	bf bt’ be’ $	(true or false) and true and true and false not (false) true	bf -> (be)
6.	(be) bt’ be’ $	(true or false) and true and true and false not (false) true	pop (
7.	be) bt’ be’ $	true or false) and true and true and false not (false) true	be -> bt be’
8.	bt be’) bt’ be’ $	true or false) and true and true and false not (false) true	bt -> bf bt’
9.	bf bt’ be’) bt’ be’ $	true or false) and true and true and false not (false) true	bf ->true
10.	true bt’ be’) bt’ be’ $	true or false) and true and true and false not (false) true	pop true
11	bt’ be’) bt’ be’ $	or false) and true and true and false not (false) true	bt’ -> ε
12	be’) bt’ be’ $	or false) and true and true and false not (false) true	be’ ->or bt be’
13.	or bt be’ ) bt’ be’ $	or false) and true and true and false not (false) true	pop or
14.	bt be’) bt’ be’ $	false) and true and true and false not (false) true	bt ->bf bt’
15.	bf bt’ be’) bt’ be’ $	false) and true and true and false not (false) true	bf -> false
16.	false bt’ be’) bt’ be’ $	false) and true and true and false not (false) true	pop false
17.	bt’ be’) bt’ be’ $	) and true and true and false not (false) true	bt’ -> ε
18.	be’) bt’ be’ $	) and true and true and false not (false) true	be’ -> ε
19.	) bt’ be’ $	) and true and true and false not (false) true	pop )
20.	bt’ be’ $	and true and true and false not (false) true	bt’-> and bf bt’
21.	and bf bt’ be’ $	and true and true and false not (false) true	pop and
22.	bf bt’ be’ $	true and true and false not (false) true	bf -> true
23.	true bt’ be’ $	true and true and false not (false) true	pop true
24.	bt’ be’ $	and true and false not (false) true	bt’ -> and bf bt’
25.	and bf bt’ be’ $	and true and false not (false) true	pop and
26.	bf bt’ be’ $	true and false not (false) true	bf -> true
27.	true bt’ be’ $	true and false not (false) true	pop true
28.	bt’ be’ $	and false not (false) true	bt’ -> and bf bt’
29.	and bf bt’ be’ $	and false not (false) true	pop and
30.	bf bt’ be’ $	false not (false) true	bf -> false
31.	false bt’ be’ $	false not (false) true	pop false
32.	bt’ be’ $	not (false) true	ditolak

http://binus.ac.id

Top-Down Parsing adalah sebuah metode dimana metode ini melakukan penelusuran dari root ke leaf atau dari simbol awal ke terminal.

Metode Top-Down Parsing ini meliputi :

1. Backtrack/ Backup      : Brute Force
2. No Backtrack                : Recursive Descent Parser

Di dalam pencarian Top–Down Parsing, terdapat beberapa permasalah yang mungkin akan ditemui :

1. Left Recursion
2. Left Recursive

Left Recursion

Sebuah grammar dikatakan bersifat left recursion apabila grammartersebut mengandung suatu nonterminal dan derivasinya.

Contoh : A → Aα

Metode Top-Down Parsing tidak bisa menangani grammar yang mengandung left recursive, sehingga left recursive perlu dihilangkan. Di bawah ini akan dijelaskan bagaimana cara menghilangkan left recursive.

Contoh 2 : A → Aα|β

Maka, A → βA’

A’ → αA’ | ε

Mengapa dalam metode Top Down Parsing tidak boleh terdapat left recursive?

Karena left recursive menyebabkan parsing mengalami looping tak hingga.

http://binus.ac.id

Untuk konversi dari RE (Regular Expression) ke DFA dapat dilakukan dengan menggunakan 2 cara, yaitu:

1. Dengan menggunakan metode Thomson’s Construction (ɛ-NFA) lalu baru ke DFA
2. Dengan menggunakan konversi ke tree terlebih dahulu

Berikut adalah contoh untuk konversinya:

RE:  ab(a|b)*ab* | ab(a|b)⁺ #

1. Dengan cara ke – 1 :

– Langkah pertama gambarkan ɛ-NFA dari RE tersebut.

– Setelah itu tentukan ɛ-closure untuk mendapatkan state pada DFA, dengan cara sebagai berikut:

S0 = ɛ-closure(0) = {0, 1, 15}

ɛ-closure(move(S0, a)) =  ɛ-closure({2, 16}) = {2, 16} = S1

ɛ-closure(move(S0, b)) =  –

ɛ-closure(move(S1, a)) =  –

ɛ-closure(move(S1, b)) =  ɛ-closure({3, 17}) = {3, 4, 5, 7, 10, 17, 18, 20} = S2

ɛ-closure(move(S2, a)) =  ɛ-closure({6, 11, 19}) = {4, 5, 6, 7, 9, 10, 11, 12, 14, 17, 18, 19, 20, 22, 23} = S3*

ɛ-closure(move(S2, b)) =  ɛ-closure({8, 21}) = {4, 5, 7, 8, 9, 10, 17, 18, 20, 21, 22, 23} = S4*

ɛ-closure(move(S3, a)) =  ɛ-closure({6, 11, 19}) =  S3*

ɛ-closure(move(S3, b)) =  ɛ-closure({8, 13, 21}) =  {4, 5, 7, 8, 9, 10, 12, 13, 14, 17, 18, 20, 21, 22, 23} = S5*

ɛ-closure(move(S4, a)) =  ɛ-closure({6, 11, 19}) =  S3*

ɛ-closure(move(S4, b)) =  ɛ-closure({8, 21}) =  S4*

ɛ-closure(move(S5, a)) =  ɛ-closure({6, 11, 19}) =  S3*

ɛ-closure(move(S5, b)) =  ɛ-closure({8, 13, 21}) =  S5*

– Selanjutnya, gambarkan state DFA tersebut:

– Selanjutnya DFA tersebut akan di minimalisasikan menjadi minimized DFA dengan cara:

Berikut adalah gambar hasil dari Minimized DFA:

2.  Dengan cara ke- 2:

– Langkah pertama tentukan follow pos dari RE tersebut:

Follow pos 1 = 2

Follow pos 2 = 3, 4, 5

Follow pos 3 = 3, 4, 5

Follow pos 4 = 3, 4, 5

Follow pos 5 = 6

Follow pos 6 = 6, 11

Follow pos 7 = 8

Follow pos 8 = 9, 10

Follow pos 9 = 9, 10, 11

Follow pos 10 = 9, 10, 11

Follow pos 11 = –

– Langkah selanjutnyagambarkan treenya dari RE tersebut untuk menentukan S0:

Didapat S0 = {1, 7}

– Selanjutnya buatlah table untuk menentukan dfanya:

	a	b
S0	2, 8 = S1	–
S1	–	3, 4, 5, 9, 10 = S2
S2	3, 4, 5, 6, 9, 10, 11 = S3*	3, 4, 5, 9, 10, 11 = S4*
S3	3, 4, 5, 6, 9, 10, 11 = S3*	3, 4, 5, 6, 9, 10, 11 = S3*
S4	3, 4, 5, 6, 9, 10, 11 = S3*	3, 4, 5, 9, 10, 11 = S4*

Untuk hasil DFA dari cara ini didapat hasilnya merupakan DFA minimizednya sehingga gambarnya menjadi:

Sekian penjelasan mengenai konversi RE ke DFA. Semoga bermanfaat untuk Anda 

http://binus.ac.id