next up previous contents
Next: 5.14 ���������� Up: 5 ���������� ��������� (���������� Previous: 5.12 ���������������   Contents

5.13 ��, 8/2/03: ������ ��� ������������ ������� �������������

����� ��� ���� �������� ������� ��� ���������.

�� ������ ��� ��������� ���� �� �������� 6 ���������� (2 ���� ��������).

  1. ������������ DFA ��� ��� ������� (�) ��� ������ ��� ${\left\{{0,1}\right\}}^*$ ��� ��������� ��� ������� 0101 (�) $ {\left\{{w\in{\left\{{a,b}\right\}}^*:    5 \mid 2A(w)+3B(w)+1}\right\}}$, ���� $A(w)$, ��� $B(w)$ ����� �� ������ ��� $a$ ��� ��� $b$ ��� ���� $w$ ��� $x\vert y$ �������� ��� �� $x$ ������� �� $y$.
  2. ������ ��� � ������ $ {\left\{{a^kb^k:   k\in{\mathbf N}}\right\}}$ ��� ����� ��������.
  3. �� $L \subseteq \Sigma^*$ ����� ��� ������ � ����� $R_L$ �������� ��: $x R_L y$ �� ��� ���� �� ��� ���� $z \in \Sigma^*$ ������

    $\displaystyle xz \in L \Leftrightarrow yz \in L, $

    ���. �� $xz$, $yz$ ���� ������� ��� �� ��� ���� $L$ ���� ������. ������ ��� � ����� $R_L$ ����� ����� �����������.
  4. ����� ��� context-free ���������� ��� �� ������ $ (01^*0^*1)^+$.
  5. ������ ��� � ������ $ {\left\{{xx:  x\in{\left\{{0,1}\right\}}^*}\right\}}$ ��� ����� context free.
  6. ������ ��� �� ������ ��� ������������ $\pi$ �� ����� ��� ����������� ��� ����� ���������� ������������. (�������� �� ��������������� �� ��� �� halting problem ��� ����� ����������� �����������.)


Mihalis Kolountzakis 2003-09-04