UAS Teori Bahasa dan Otomata 2025

1. CNF dan bahasa

Dari gambar, produksi awal adalah S → AB | aB, A → abb | λ, dan B → bbA. Karena A dapat kosong, eliminasi λ serta produksi unit yang timbul. Salah satu bentuk normal Chomsky yang ekuivalen:

S → AB | CA | YY | XB
A → XC
B → CA | YY
C → YY
X → a
Y → b

Semua ruas kanan berbentuk dua nonterminal atau satu terminal. Bahasa asal berhingga: pilihan A pertama dan terakhir masing-masing abb atau kosong, sedangkan alternatif kedua memakai awalan a. Jadi L = {bb, bbabb, abbbb, abbbbabb, abb, abbabb}. Contoh S → AB → abb B → abb bb A → abbbb.

2. Parser dan compiler

Gambar memuat ekspresi a/b + (a-b)*c, dengan E → T | E+T | E-T, T → F | T*F | T/F, F → I | (E), I → a | b | c. Pemindai menghasilkan token a / b + ( a - b ) * c. Pohon abstraknya:

          +
        /   \
       /     *
      / \   / \
     a   b -   c
          / \
         a   b

Parser menerapkan aturan E → E + T, ruas kiri T → T / F, dan ruas kanan T → T * F dengan faktor (E) yang memuat E → E - T. Kode tiga alamat yang sesuai:

t1 = a / b
t2 = a - b
t3 = t2 * c
t4 = t1 + t3

Lexer mengenali identifier dan operator; parser memeriksa struktur; analisis semantik memeriksa tipe dan dapat mengatur pemeriksaan pembagian nol saat eksekusi; generator menghasilkan urutan operasi. Ini adalah contoh implementasi alur compiler, bukan nilai numerik karena nilai a, b, c tidak diberikan.

Implementasi berikut menghilangkan rekursi kiri pada grammar menjadi loop asosiatif kiri: E → T ((+|-) T)*, T → F ((*|/) F)*, dan F → I | (E). Ia memeriksa seluruh masukan dan menghasilkan kode tiga alamat untuk ekspresi soal.

import re

def compile_expression(source):
    tokens = re.findall(r"[abc]|[+*/()-]|\S", source)
    position, code = 0, []

    def take(token=None):
        nonlocal position
        if position >= len(tokens) or (token is not None and tokens[position] != token):
            raise ValueError(f"Token tidak sesuai pada posisi {position}")
        value = tokens[position]
        position += 1
        return value

    def emit(op, left, right):
        target = f"t{len(code) + 1}"
        code.append(f"{target} = {left} {op} {right}")
        return target

    def factor():
        if position < len(tokens) and tokens[position] == '(':
            take('(')
            result = expression()
            take(')')
            return result
        value = take()
        if value not in ('a', 'b', 'c'):
            raise ValueError(f"Identifier tidak dikenal: {value}")
        return value

    def term():
        left = factor()
        while position < len(tokens) and tokens[position] in ('*', '/'):
            op = take()
            left = emit(op, left, factor())
        return left

    def expression():
        left = term()
        while position < len(tokens) and tokens[position] in ('+', '-'):
            op = take()
            left = emit(op, left, term())
        return left

    result = expression()
    if position != len(tokens):
        raise ValueError(f"Token tersisa: {tokens[position]}")
    return code, result

instructions, result = compile_expression('a/b + (a-b)*c')
print('\n'.join(instructions))

Pemeriksaan nilai pembagi tidak selalu dapat dilakukan saat kompilasi karena nilai variabel belum diketahui; pemeriksaan pembagi nol dapat disisipkan atau dilakukan pada waktu eksekusi. Kode contoh menghasilkan tepat t1 sampai t4 di atas dan menolak sintaks di luar grammar.

3. Bahasa PDA

Stack menyimpan kelebihan simbol yang belum dipasangkan: a di atas stack dibatalkan oleh input b, dan sebaliknya. Karena perpindahan ke final q1 hanya saat penanda dasar Z muncul setelah input habis, bahasa yang diterima adalah semua string atas alfabet a,b dengan jumlah a sama dengan jumlah b, termasuk λ. Misalnya:

(q0, abba, Z) ⊢ (q0, bba, aZ) ⊢ (q0, ba, Z)
              ⊢ (q0, a, bZ) ⊢ (q0, λ, Z) ⊢ (q1, λ, Z)

4. Mesin Turing

Mesin mengganti semua 1 awal dengan x saat bergerak ke kanan. Kemudian ia berulang kali memulihkan satu x menjadi 1 dan menambahkan satu 1 di ujung kanan; ketika tidak ada x lagi ia mencapai q3. Jadi pada input unary 1ⁿ, keluarannya 1²ⁿ (n ≥ 0). Simbol x dipakai oleh transisi meskipun daftar alfabet pita pada naskah tidak mencantumkannya; agar mesin konsisten, tambahkan x ke alfabet pita.

Untuk input 11, dengan state ditulis tepat sebelum simbol yang dipindai dan □ sebagai blank:

q0 11 ⊢ x q0 1 ⊢ xx q0 □ ⊢ x q1 x
⊢ x1 q2 □ ⊢ x q1 11 ⊢ q1 x11
⊢ 1 q2 11 ⊢ 11 q2 1 ⊢ 111 q2 □
⊢ 11 q1 11 ⊢ 1 q1 111 ⊢ q1 1111
⊢ q1 □1111 ⊢ q3 1111

Pembacaan q1 bergerak melewati 1 ke kiri sampai blank, lalu q3 berhenti di awal hasil.