AUTOMATA THEORY
AND FORMAL LANGUAGES
Teori Bahasa dan Automata
Profile
• Mutia Fadhilla, S.S.T., [Link].
• Pendidikan
• D4 – Politeknik Caltex Riau – Teknik Informatika
• S2 – Dayeh University Taiwan – Computer Science and Information Engineering
• Kontak
• [Link] / WA / Telegram : +62 813 2036 5348
• Email : tiafadhilla@[Link]
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 2
ATURAN KULIAH, RPS, PENILAIAN
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 3
Aturan Perkuliahan
• Mahasiswa yang tidak kuliah 3 kali berturut turut dari awal tidak dibenarkan mengikuti
perkuliahan selanjutnya
• Kehadiran Minimal hadir 75% dari tatap muka
• Kuliah dilakukan secara offline / tatap muka
• Pakaian rapi dan sopan sesuai aturan kampus
• Handphone mode silence / non-aktif (dosen & mahasiswa)
• Dilarang makan di kelas, minuman ringan diperbolehkan
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 4
Keterlambatan
• Toleransi Dosen / Mahasiswa : 15 Menit
• Pengecualian :
• Kondisi cuaca hujan.
• Kondisi tidak diduga di perjalanan seperti ban kendaraan bocor, kendaraan mogok, dan lainnya.
• Sanksi Keterlambatan :
• Dosen : Kelas dibatalkan (Kecuali ada pemberitahuan sebelumnya)
• Mahasiswa : Boleh ikut kuliah, tetapi tidak absen
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 5
Penilaian
1) Tugas : 30%
2) UTS : 25%
3) UAS : 25%
4) Quiz : 10%
5) Absensi : 10%
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 6
Range Nilai
ANGKA NILAI BOBOT HURUF KETERANGAN
>80 4 A Sangat Baik Sekali
75 < x ≤ 80 3,75 A- Baik Sekali
70 < x ≤ 75 3,5 B+ Amat Baik
60 < x ≤ 70 3 B Baik
55 < x ≤ 60 2,75 B- Baik
50 < x ≤ 55 2,5 C+ Cukup
40 < x ≤ 50 2 C Cukup
35 < x ≤ 40 1.75 C- Kurang
30 < x ≤ 35 1 D Kurang Sekali
<30 0 E Gagal
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 7
Rencana Perkuliahan Semester (RPS)
P Materi Tugas
1 RPS, Kontrak Kuliah, Pengenalan Mata Kuliah
2 Deterministic & Non-deterministic Finite Automata (DFA & NFA) ✓
3 Regular Expression (RE)
4 εNFA , Regular Expression to εNFA ✓
5 εNFA to NFA
6 NFA to DFA ✓
7 Quiz (Kisi-kisi UTS) *Quiz
UTS
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 8
Rencana Perkuliahan Semester (RPS)
P Materi Tugas
9 NFA/DFA to Regular Expression
10 Context Free Grammar (CFG) ✓
11 Pushdown Automata (PDA)
12 CFG to PDA ✓
13 Turing Machine
14 Automata Implementation (Compiler)
15 Quiz (Kisi-kisi UAS) *Quiz
UAS
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 9
Referensi
• D. Suryadi HS. Pengantar Automata Bahasa Formal Dan Kompilasi. Jakarta : Gunadarma.
• Adi Sulistyo Nugroho. Pengantar Teori Bahasa & Otomata. Yogyakarta : Graha Ilmu. 2013
• Hopcroft, John E., Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and
Computation. Massachusetts: Addison Wesley Publishing Company. 1979.
• John Martin. Introduction to Languages and the Theory of Computation. New York:
McGraw-Hill. 2003.
• Peter Linz. An Introduction to Formal Language and Automata. Canada : Jones & Bartlett
Learning. 2012.
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 10
Google Classroom
[Link]
• Materi Kuliah
• Pengumpulan Tugas
• Nilai Proses (Tugas, Quiz, UTS, UAS)
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 11
Pengumpulan Tugas
• Tugas paling lambat dikumpul 7 hari / seminggu setelah tugas diberikan
• Kompensasi Keterlambatan:
• 1 Hari : dimaafkan
• 2 – 10 Hari : nilai tugas akan berkurang 5 poin / hari
• > 10 Hari : nilai tugas = 0 (dianggap tidak mengerjakan tugas)
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 12
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 13
AUTOMATA THEORY & FORMAL LANGUAGE
INTRODUCTION
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 14
AUTOMATA
What is automata?
• Automata is an abstract model of a computational machines /
devices
• Abstract devices are simplified models of real computations
• Computations could be happened in everywhere : laptop,
smartphones, other electronic devices, in nature, …
• Why we need abstract model?
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 16
A Simple “Device”
H
W ITC
S
input: switch
output: light bulb
actions: flip switch
states: on, off
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 17
A Simple “Device”
H
W ITC
S
start off on
input: switch
bulb is on if and only if
output: light bulb
there was an odd
actions: flip switch number of flips
states: on, off
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 18
Another “Device”
1
• inputs: switches 1 and 2
• actions: 1 for “flip switch 1”
• actions: 2 for “flip switch 2”
• states: on, off
2
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 19
Another “Device”
1 1
start off off
1
2 2 2 2
2
1
• inputs: switches 1 and 2 off on
1
• actions: 1 for “flip switch 1”
• actions: 2 for “flip switch 2” bulb is on if and only if both
• states: on, off switches were flipped an
odd number of times
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 20
Design Problem
1 4
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 21
Design Problem
• How to design the devices?
• It can be designed in an infinite number of ways
• Such devices are difficult to think and reason about
• Representing them as abstract computational devices (automata)
• We can learn how to answer such questions
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 22
Automata Can Model Anything
• It can describe the operation of any “small computer” such as
microwave, oven, alarm clock, vending machine and rice cooker.
• The "lexical analyzer" of a typical compiler, that is, the compiler
component that breaks the input text into logical units, such as
identifiers, keywords, and punctuation.
t h e n
start t th the then
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 23
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 24
Different Kinds of Automata
Devices with a finite amount of memory.
Finite Automata Used to model “small” computers.
Push-down Automata Devices with infinite memory that can be accessed in a restricted way.
Used to model parsers, etc.
Turing Machines Devices with infinite memory.
Used to model any computer.
Time-bounded Infinite memory, but bounded running time.
Turing Machines Used to model any computer program that runs in a “reasonable” amount
of time.
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 25
FORMAL LANGUAGE
Alphabets and Strings
• A common way to talk about words, number, pairs of words, etc. is by
representing them as strings
• To define strings, we start with an alphabet (a finite set of symbols)
• Examples: S1 = {a, b, c, d, …, z}: the set of letters in English
S2 = {0, 1, …, 9}: the set of (base 10) digits
S3 = {a, b, …, z, #}: the set of letters plus the special symbol #
S4 = {(, )}: the set of open and closed brackets
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 27
Strings
• A string over alphabet S is a finite sequence of symbols in S.
• The empty string will be denoted by e
• Examples: cfghw is a string over S1 = {a, b, c, d, …, z}
2486 is a string over S2 = {0, 1, …, 9}
mn#nm is a string over S3 = {a, b, …, z, #}
))()(() is a string over S4 = {(, )}
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 28
Languages
• A language is a set of strings
• Languages can be used to describe problems with “yes/no” answers, for
example:
S1 = {a, b, c, d, …, z}: the set of letters in English
S2 = {0, 1, …, 9}: the set of (base 10) digits
L1 = The set of all strings over S1 that contain the substring “spoon”
L2 = The set of all strings over S2 that are divisible by 7
{7, 14, 21, …}
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 29
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 30
11-Sep-22 GA22/23 - TBA - Mutia Fadhilla, [Link]., [Link] 31
