Next: 5.14 ����������
Up: 5 ���������� ��������� (����������
Previous: 5.12 ���������������
Contents
����� ���
���� �������� ������� ��� ���������.
�� ������ ��� ��������� ���� �� �������� 6 ���������� (2 ���� ��������).
- ������������ DFA ��� ��� ������� (�) ��� ������ ���
��� ��������� ��� ������� 0101
(�)
,
����
, ���
����� �� ������ ���
��� ���
��� ����
���
�������� ��� ��
������� ��
.
- ������ ��� � ������
��� ����� ��������.
- ��
����� ��� ������ � �����
�������� ��:
�� ��� ���� �� ��� ����
������
���. ��
,
���� ������� ���
�� ��� ����
���� ������.
������ ��� � �����
����� ����� �����������.
- ����� ��� context-free ���������� ��� �� ������
.
- ������ ��� � ������
��� ����� context free.
- ������ ��� �� ������ ��� ������������
�� ����� ��� ����������� ��� ����� ���������� ������������.
(�������� �� ��������������� �� ��� �� halting problem ��� ����� ����������� �����������.)
Mihalis Kolountzakis
2003-09-04