�v���O��������̋L�q

�\��(syntax)�A�Ӗ�(semantics)
  1. �\���L�q�@
  2. �������R���@ CFG
    CFG ���ۂ̃v���O��������ł� Context-free �ł� �Ȃ����A���@�K��̒��j�Ƃ��ďd�v�B
    ���p�I�Ȑ����̍\����CFG�ɓK������B
    �\���P�ʂ̍\���̍ۂɓ����\�����O���\���Ɩ��֌W�B
    CFG �ɂ‚��Ă̏����n�ɂ��F���ȂǗ��_�E�Z�@�������Ă���B
    CFG�Ƃ́A���̂S�‘g
    G = < V, ��, P, S >
    �ł���B������
    1. V ��G����b(vocabulary)�ƌĂԗL���W���B
      ���̗v�f��G���L��(symbol)�B
    2. �� ��V �̕����W���ŁAG �������W(alphabet)�B
      ���̗v�f
      G ������ �I�[�L��(terminal symbol)
      V - ���̗v�f
      �\���P��(syntactic unit) �\���ϐ�(syntactic variable) ��I�[�L��(nonterminal symbol)�Ƃ����B
    3. P ��G �������K���W(set of poduction rules)
      G�̍\���P��A �� V ��̋L������ �� �Ή������鏇���� <A,��>��
      A �� ��
      �̌`�ɏ��������́B
    4. S �͍\���P�ʂ̈�‚ŁAG ���J�n�L��(start symbol)

    �A��
    ���� �� �� �� �� ���A��
    ���o
    �� �� �Ё� A �̏o���ɒ��ڂ��A ���Œu�������鑀��
    ����
    ��0 = S ����̓��o�œ�������̂̑S�� L(G)
    ���@G ���������ꂽ����

    �� 2�i����`0'��`1'����ׂ�2�i���ŁA3�̔{���ɂȂ���̂𐶐�����CFG

    �� = {0,1};
    VN = V - ��
    = {M, M0, M1, M2 };
    P = {M �� 0,
    M �� M0, M1 �� 1,
    M0 �� M11, M0 �� M00,
    M1 �� M01, M1 �� M20,
    M2 �� M10, M2 �� M21 };
    S = M
  3. BNF
    1. ��I�[�L���� < > �ň͂�ŕ\���B
    2. �I�[�L���̓v���O�����Ɏg���镶���������B
    3. �����K���� `::=' ���g���ď����B�������ӂ̍\���P�ʂɐ����K���� �Q�ˆȏ゠��ꍇ�� `|' (���Ăڂ�) �ŋ�؂��ĕ��ׂ�B
    3�̔{���ł���2�i���𐶐����� BNF
    <3�̔{��> ::= 0 | <����3�̔{��>
    <����3�̔{��> ::= <����3�̔{��>0 |
    <3�̔{������1>1
    <3�̔{������1> ::= <����3�̔{��>1|
    <3�̔{������2>0
    <3�̔{������2> ::= <3�̔{������1>0 |
    <3�̔{������2>1
  4. �\���} �\���𗬂�}���ɕ`�������́B

    ��F3�̔{���ł���2�i���̍\���}

���ۂ̍\���L�q�̗�F

�V���o�X�֖߂�