Soal :

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?

Jawaban :

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 lingkaran”
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

 

http://binus.ac.id

1. Perusahaan tambang yang sedang melakukan eksplorasi melakukan penelitian kandungan emas disuatu tempat. Berdasarkan hasil penelitian, kandungan emas mengikuti jalur lintasan y=f(x) = e^x  . Menurut data satelit, untuk mendapatkan kandungan emas terbanyak ada di posisi x=0.4. Jika posisi pengeboran tersebut dihitung menggunakan pendekatan deret Taylor sampai dengan 4 suku pertama, hitunglah ( pembulatan 4 angka dibelakang koma),Hitunglah :
2. Seorang pembuat boneka ingin membuat dua macam boneka yaitu boneka A dan boneka B. Kedua boneka tersebut dibuat dengan menggunakan dua macam bahan yaitu potongan kain dan kancing. Boneka A membutuhkan 10 potongan kain dan 6 kancing, sedangkan boneka B membutuhkan 8 potongan kain dan 8 kancing. Permasalahannya adalah berapa buah boneka A dan boneka B yang dapat dibuat dari 82 potongan kain dan 62 kancing ? Selesaikan dengan metode gauss-Jourdan !
3. Carilah nilai  x₁, x₂ dan x₃  dari sistem persamaan linear berikut dengan menggunakan metode  dekomposisi LU.

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 grammar tersebut 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.

Left Factoring

Grammar dapat dikatakan left factoring apabila terdapat produksi yang berbentuk seperti di bawah ini :

Contoh 3 :

A → αβ₁ | αβ₂

Grammar tersebut diubah menjadi :

A → αA’

A’ → β₁ |β₂

Adanya left factoring ini menyebabkan grammar menjadi ambigu karena tidak jelas yang mana dari dua produksi alternatif yang bisa digunakan untuk memperluas nonterminal A. Dari contoh soal di atas, kita tidak tahu mau menelusuri A ke αβ₁ atau ke αβ_2.

Demikian penjelasan singkat mengenai Top-Down Parsing, good luck! 😀

http://binus.ac.id

Jaringan adalah sebuah kumpulan komputer yang saling terhubung satu dengan yang lainnya dan dapat berkomunikasi, bertukar informasi, bertukar file, dan lain-lain.

 

Cara mengubah RE menjadi DFA dengan menggunakan dua cara, yaitu :

1. Tree
2. ε-NFA

Constraint:

• State dari DFA minimal 5 state maksimal 8 state.
• Final state minimal 2 state dan maksimal 3 state.

Contoh Soal :

Solusi :

1.  Menggunakan cara tree

Dari tree tersebut, dapat kita tentukan S₀ nya adalah 1. Kemudian buatlah followpost dengan menggunakan indeks yang berurutan dari soal RE di atas.

Followpost 1 = 2, 4, 5, 6
Followpost 2 = 3
Followpost 3 = 2, 4, 5, 6
Followpost 4 = 4, 5, 6
Followpost 5 = 4, 5, 6
Followpost 6 = 7
Followpost 7 = 6, 8
Followpost 8 = –

Tabel Follow Post yang dibuat membantu kita untuk menentukan DFA. Final State ditentukan dari state yang terdapat tanda “#”, dimana tanda tersebut merupakan tanda untuk Final State.

Maka DFA yang ditemukan dari soal tersebut adalah :

2.  Menggunakan cara ε-NFA

ε-NFA dari soal di atas :

Kemudian carilah ε-closure move-nya :

ε-closure (0) = 0 → {S₀}
ε-closure (move(S₀, a)) = ε-closure {1} = {1, 2, 5, 6, 7, 9, 12} → {S₁}
ε-closure (move(S₀, b)) = {}
ε-closure (move(S₁, a)) = ε-closure {3, 8, 13} = {3, 6, 7, 8, 9, 11, 12, 13} → {S₂}
ε-closure (move(S₁, b)) = ε-closure {10} = {6, 7, 9, 10, 11, 12} → {S₃}
ε-closure (move(S₂, a)) = ε-closure {8, 13} = {6, 7, 8, 9, 11, 12, 13} → {S₄}
ε-closure (move(S₂, b)) = ε-closure {4, 10, 14} = {2, 4, 5, 6, 7, 9, 10, 11, 12, 14} → {S₅*}
ε-closure (move(S₃, a)) = ε-closure {8, 13} = {S₄}
ε-closure (move(S₃, b)) = ε-closure {10} ={S₃}
ε-closure (move(S₄, a)) = ε-closure {8, 13} = {S₄}
ε-closure (move(S₄, b)) = ε-closure {10, 14} = {6, 7, 9, 10, 11, 12, 14} → {S₆*}
ε-closure (move(S₅, a)) = ε-closure {3, 8, 13} = {S₂}
ε-closure (move(S₅, b)) = ε-closure {10} = {S₃}
ε-closure (move(S₆, a)) = ε-closure {8, 13} = {S₄}
ε-closure (move(S₆, b)) = ε-closure {10} = {S₃}

Kemudian dapat dibuat tabel seperti berikut :

Dari tabel ε-closure move, ditemukan DFA graph sebagai berikut :

Dari kedua cara yang dikerjakan yaitu dengan menggunakan tree dan ε-NFA ditemukan dua grafik DFA yang sama. Setelah grafik DFA ditemukan kemudian cari DFA Minimized.

Pertama-tama kita lakukan pemisahan state di dalam DFA, pisahkan antara state biasa dan final state. Ditemukan tabel seperti di bawah ini :

Kemudian dari tabel ini buatlah grafik DFA-Minimized :

Demikian cara-cara mengubah RE (Regular Expression) menjadi DFA dan DFA Minimized.

Semoga bermanfaat. Thank you 🙂

http://binus.ac.id

Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂