2-Theory


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
1.

Стеков автомат

Стеков автомат наричаме наредената шесторка
M =


K
͕ Σ͕ Γ͕ Δ͕
S, F�,

където
K


крайно множество от
състояния͕ Σ


крайна азбука

на езика͕ който разпознава
M
͕ Γ


стекова азбука͕ Δ ≤ (
K x (
Σ



{ε}) x
Γ*
)
x (K x
Γ*
)


релация на преходите͕
S



K


начално състояние
, F


K


множество от финални

(заключителни)

състояния
.

2.

|
-
M

за стеков автомат M

(едностъпково преобразувание)

За стековия автомат
M

=
K
͕ Σ͕ Γ͕ Δ͕
S, F�,
|
-
M

дефинираме така͗


(
p͕ x͕ α)
|
-
M

(q͕ y͕ ω) <=>
съществува ((
p͕ a͕ β)͕ (q͕ γ))


Δ

и е изпълнено͗


x = ay;

α = βη͖

ω = γη
за някое η


Γ*͘

|
-
M
*
наричаме рефлексивното и транзитивното затваряне на
|
-
M
.

3.

Прост стеков автомат

Прост стеков автомат наричаме наредената шесторка
A =

K
͕ Σ͕ Γ͕ Δ͕
�S, F,
такъв͕ че за всяко правило
(
(
q,
a
,
β
)
,
(
p͕ γ))



Δ

и
q



s,
е изпълнено
β


Γ

и
|γ| ≤ 2͘

4.

Кога една дума се приема от стеков автомат

Казваме͕ че стековият автомат
M =


K
͕ Σ͕ Γ͕ Δ͕
S,� F

приема думата ω͕ ако е изпълнено
(s͕ ω͕ ε)

|
-
M
* (f͕ ε͕ ε)͕ f


F.

5.

Граматика в нормална форма на иомски

Казваме͕ че контекстно свободната граматика
G =
е в нормална форма на иомски͕ ако е изпълнено
R ≤ (V
\

Σ) x V
2
.

6.

Машина на аюринг

Машина на аюринг наричаме наредената петорка
M = K,
Σ
,
δ
, S,� H,
където
K


крайно
множество от
състояния͕
Σ



азбука͕

която задължително съдържа
символи
те


(ляв ограничител) и


(празна клетка)͕ но не
съдържа символите


и


;
H


K


множество
от стоп
-
състояния͕
S


K


начално
състояние и
δ



функция
на преходитеǣ


δ
: (
K
\

H) x
Σ



K x (
Σ



{

,

})
,

за която


а)
ако

за всяк
о

q


(K
\

H),
δ
(q,
) = (p,
b
)

=� b

=



б)
ако за всяко

q


(K
\

H)

и
a


Σ
,

δ
(q, a) = (p, b) =�
b



7.

Кога една машина на аюринг разпознава един език

Езикът
L
се разпознава от машината на аюринг
M =
,
ако
:


а) ако
ω



L,
то
ω

се приема от
M
;


б)
ако
ω



L,
то
ω

се отхвърля от
M
.

8.

Кога една машина на аюринг изчислява една функция на
k
променливи

Казваме͕ че машината на аюринг
M =

изчислява функцията на
k
променливи
f: N
k



N,
ако
n
1
, n
2
,

...
,

n
k


N

и
:


а)
ако
f(
n
1
,
...
,

n
k
)
е дефинирана͕ то
(

,


1

1

1

2

ǥ

1


|



(

,


1

(

1
,
ǥ
,


)
;


б
) ако
f(n
1
,

͙͕ n
k
)
не е дефинирана
͕ то

M(
1
n1

˽

͙

˽

1
nk
)

???

9.

Операцията минимизация

Н
ека
f: N
n+1



N,
частично дефинирана функция
͘ Казваме͕ че
ф
-
ята

g
се получава

от
f
с помощта на
μ
-
операция
(минимизация)͕ ако за произволни

x
1
,

͙
, x
n
, y, z


N
са изпълнени следните условияǣ
g(
x
1
,

͙
, x
n
)


y
=00;=

а
) f
(
x
1
,

͙
, x
n
,

y
)
= 0
;

б)


z y
е дефинирана f
(
x
1
,

͙
, x
n
,

z
)

и
f
(
x
1
,

͙
, x
n
,

z
)

� 0.

10.

Операцията примитивна рекурсия

Нека имаме
f: N


N
частично дефинирана ф
-
я
и
g:
N
3



N
частично дефинирана ф
-
я
.
Казваме͕ че ф
-
ята
h
се
получава от
f
и
g
с помощта на примитивна рекурсия͕ ако


x, y


N

е

в силаǣ

h(x, 0)


f(x)

h(x, y + 1)


g(h(x, y), x, y)

11.

Примитивно рекурсивна функция

Индуктивна дефиниция за примитивно рекурсивна функция͗


а)
f


{
O, S,



}

са ПРФ
;


б) ако
f, g
1
, g
2
,
ǥ
, g
k

са

примитивно рекурсивн
и

функци
и
, то
функцията
h,
която се получава от тях
с пом
ощта на операцията суперпо
зиция, също
е
ПРФ
;


в) ако
f, g
са ПРФ и ф
-
ята
h
се получава от
f
и
g
чрез операцията примитивна рекурсия, то
h
е
ПРФǤ

12.

Частично рекурсивна функция

Индуктивна дефиниция за частично рекурсивна функция
:


а)
O, S,




са иРд
;


б) ако
f, g
1
, g
2
,
͙͕ g
n
са частично рекурсивни функции͕ то
функцията
h,
която се получава от тях с
пом
ощта на операцията суперпо
зиция͕ също е иРд
;


в)
ако
f

и
g

са частично рекурсивни функции͕

то функцията
h,
която се получава от тях с операцията
частична рекурсия͕ съшо е иРд͖


г)
ако
f
е частично рекурсивна функция͕ то и
g,
която се получава от
f
с
μ
-
операция͕ също е иРд͘

13.

Какво и в какво преобразува
простата машина на аюринг
L




1


2







1


2

Без
черта Lu/Ru се движат наляво/надясно докато стигнат празен символ͘ Ако е с черта се движат
наляво/надясно докато стигнат символ различен от празния
.

14.

К
акво и в какво преобразува про
стата машина на аюринг
R




1


2






1


2


Без
черта Lu/Ru се движат наляво/надясно докато стигнат празен символ͘ Ако е с черта се движат
наляво/надясно докато стигнат символ различен от празния
.



15.

Лема
за разрастването на грамат
ични

дървета

Нека
L
е език͕ който се поражда от
контекстно
-
свободна граматика

G =
͘ аогава за всяка дума ω


L,
такава͕ че
|ω|


д(
G)
|V

\

Σ
|

съществуват думи
u, v, x, y, z


Σ
*,
такива, чеǣ

1)

ω

=
uvxyz
;

2)

|vy|


1

/ vy


ε
;

3)



i



N
е изпълнено
uv
i
xy
i
z


L.

16.

авърдения

за разрешимите и полуразрешимите езици

1)

А
ко

L
е разрешим͕ то
L
е полуразрешим
;

2)

Ако
L
е разрешим͕ то
/L
е разрешим͘

17.

аеорема за неразрешимите проблеми на машината на аюринг свързани със стоп
-
проблема͕ празната
дума и
съществуването на вход

Следните проблеми на машината на аюринг са неразрешими͗

1)

Дали за дадена машина на аюринг
M
и вход
ω
, M(
ω
)

;

2)

Дали за дадена машина на аюринг
M, M
спира върху вход празната дума͖

3)

Дали за дадена машина на аюринг
M, M
спира върху поне един вход (т͘е͘ дали съществува
ω
͕ за
което
M(
ω
)

).

18.

аеорема

за неразрешимите проблеми на машината на аюринг свързани
с всек
и вход͕ две машини на
аюринг и регулярните езици

Следните проблеми на машината на аюринг са неразрешими͗

1)

Дали за дадена машина на аюринг
M, M
спира за всеки вход (т͘е͘
M(
ω
)


за всяко
ω
);

2)

Дали за дадени машини на аюринг
M
1

и
M
2
,
M
1

и
M
2

спират върху един и същ

вход͖

3)

За дадена машина на аюринг
M,
дали
L(M)
е регулярен͘


Приложенные файлы

  • pdf 23761538
    Размер файла: 366 kB Загрузок: 0

Добавить комментарий