Специальная математика. Соловьев А.Е. - 74 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

K c
Построим дерево вывода.
Для предложения a * b + c дерево вывода будет:
I
I T
T M
T * M K
M K c
a b
Этот же результат можно получить и другим способом:
I I + I
I I - I I
I I*I
I I/I I + I
I (I)
I a I * I c
I b
I c a b
7.3. Классификация языков по Хомскому
Н. Хомский предложил подразделять формальные грамматики, как и порождаемые ими
языки на четыре типа.
Тип 0 - формальная грамматика, на правила которой не накладывается никаких
ограничений. Для исследования они интереса не представляют – поскольку режим «делай,
что хочешь» для математики и для практики редко представляют интерес.
Тип 1 . К этому типу относятся грамматики, правила которых имеют вид:
vw ::= vw, где
v, w V
*
- произвольные цепочки символов, возможно пустые;
V
N
- нетерминальный символ;
V
*
\{} [ иногда V
*
].
[ V
*
].
Эти грамматики еще называют контекстно-зависимыми или КЗ-грамматиками.
Здесь строка заменяется на строку в рамках какого-то контекста. Часто используется на
практике подмножество таких грамматик, называемое грамматиками непосредственных
составляющих:
vAw ::= vw, где v,w, V
*
, AV
N
При этом часто рассматриваются неукорачивающиеся грамматики (что обеспечивается
непустой цепочкой ).
Тип 2 . К этому типу относятся грамматики, правила которых имеют вид:
— 74 —
Kc
Построим дерево вывода.
Для предложения a * b + c дерево вывода будет:

                              I

           I                                     T

          T                                      M

    T      *      M                              K

    M             K                              c

    a             b

Этот же результат можно получить и другим способом:
II+I
II-I                                        I
I  I*I
I  I/I                               I      +          I
I  (I)
Ia                             I      *    I           c
Ib
Ic                             a            b
                      7.3. Классификация языков по Хомскому

Н. Хомский предложил подразделять формальные грамматики, как и порождаемые ими
языки на четыре типа.

Тип 0 - формальная грамматика, на правила которой не накладывается никаких
ограничений. Для исследования они интереса не представляют – поскольку режим «делай,
что хочешь» для математики и для практики редко представляют интерес.

Тип 1 . К этому типу относятся грамматики, правила которых имеют вид:
vw ::= vw,     где
  v, w  V - произвольные цепочки символов, возможно пустые;
           *

    VN - нетерминальный символ;
    V*\{} [ иногда   V* ].
  [   V* ].
Эти грамматики еще называют контекстно-зависимыми или КЗ-грамматиками.
Здесь строка  заменяется на строку  в рамках какого-то контекста. Часто используется на
практике подмножество таких грамматик, называемое грамматиками непосредственных
составляющих:
vAw ::= vw, где v,w, V* , AVN
При этом часто рассматриваются неукорачивающиеся грамматики (что обеспечивается
непустой цепочкой ).

Тип 2 . К этому типу относятся грамматики, правила которых имеют вид:

                                        — 74 —

Страницы