Automata terikat linier (Liner Boinded Automata), adalah mesin Turing non-deterministik multi-track dengan pita beberapa panjang terbatas terbatas.
Panjang = fungsi (Panjang string input awal, konstan c)
Sini,
Informasi memori ≤ c × Informasi input
Perhitungan dibatasi pada area yang dibatasi konstan. Alfabet input berisi dua simbol khusus yang berfungsi sebagai penanda ujung kiri dan penanda ujung kanan yang berarti transisi tidak bergerak ke kiri dari penanda ujung kiri atau ke kanan penanda ujung kanan rekaman.
Otomat yang dibatasi linear dapat didefinisikan sebagai 8-tupel (Q, X, ∑, q 0 , ML, MR, δ, F) di mana -
- Q adalah seperangkat status terbatas
- X adalah alfabet rekaman
- ∑ adalah alfabet input
- q 0 adalah kondisi awal
- M L adalah penanda ujung kiri
- M R adalah penanda ujung kanan di mana M R ≠ M L
- δ adalah fungsi transisi yang memetakan setiap pasangan (negara, simbol pita) ke (negara, simbol pita, Konstan 'c') di mana c dapat berupa 0 atau +1 atau -1
- F adalah himpunan status akhir
Otomat terikat linear deterministik selalu peka konteks dan otomat terikat linier dengan bahasa kosong tidak dapat ditentukan .
referensi :
Tidak ada komentar:
Posting Komentar