2013-05-15
Practice Final #6.
Originally Posted By: chris.ellis
6. Prove ALBA is decidable. Show all necessary lemmas.
Lemma:
Let M be an LBA with q states and g symbols in the tape alphabet. There are exactly qng^n distinct configurations of M for a tape of length n.
Algorithm that decides ALBA is as follows:
On input , where M is an LBA and w is a string:
1. Simulate M on w for qng^n steps or until halts.
2. if M has halted, accept if it accepted and reject if rejected. If it has not halted, reject.
Essentially, because an LBA will always have a finite number of configurations (qng^n), and because of the nature of the algorithm, it will always either accept or reject if halted after the qng^n number of steps. If it does not halt it will still reject and therefore is decidable
Hun Wie
David Do
Christopher Ellis
Steven Bui
Lemma:
Let M be an LBA with q states and g symbols in the tape alphabet. There are exactly qng^n distinct configurations of M for a tape of length n.
Algorithm that decides ALBA is as follows:
On input , where M is an LBA and w is a string:
1. Simulate M on w for qng^n steps or until halts.
2. if M has halted, accept if it accepted and reject if rejected. If it has not halted, reject.
Essentially, because an LBA will always have a finite number of configurations (qng^n), and because of the nature of the algorithm, it will always either accept or reject if halted after the qng^n number of steps. If it does not halt it will still reject and therefore is decidable
Hun Wie
David Do
Christopher Ellis
Steven Bui
'''Originally Posted By: chris.ellis'''
6. Prove ALBA is decidable. Show all necessary lemmas.<br><br>Lemma:<br><br>Let M be an LBA with q states and g symbols in the tape alphabet. There are exactly qng^n distinct configurations of M for a tape of length n.<br><br>Algorithm that decides ALBA is as follows:<br>On input , where M is an LBA and w is a string:<br><br>1. Simulate M on w for qng^n steps or until halts.<br>2. if M has halted, accept if it accepted and reject if rejected. If it has not halted, reject.<br><br>Essentially, because an LBA will always have a finite number of configurations (qng^n), and because of the nature of the algorithm, it will always either accept or reject if halted after the qng^n number of steps. If it does not halt it will still reject and therefore is decidable<br><br>Hun Wie<br>David Do<br>Christopher Ellis<br>Steven Bui
(c) 2024 Yioop - PHP Search Engine