Романов В.Ф. Математическая логика и теория алгоритмов. Задачник
Подождите немного. Документ загружается.
.цaнI{ьIr
и ollисaниe
кollечнoгo aBтoМaтa кoнкpeTlroй МaIIIи[tьt' зaIIисaнI{ьIе
Ha ЛенTе УМТ.
l 4. Пpимеpьr
yкaзaнньIх
зaдav
(соoтвотственнo):
.
пopaзpя,ц,нoе оyMмиpoвaниe
двol-lчI{ьlx
чl,lсел
с гtpollЗBoльньIМ числolr4
paЗpя.цoв;
.IlpoBepкa
прaвиЛьнoсTи
скoбoчнoгo вЬtpa)кения
пpoltзвoльнoй
длI,rньI;
.
пpoблeМa
paспoзнaЬaнlu urлгoр}IтМoB.
15, БAЗA:
"(
)u
_
trpaвиЛьнoе
скoбoчноe вЬIрaжение
(ПсB).
PЕКУPCИJI:
a) Если
l
_
ПСB, тo и
(l)
_
ПCB.
b)Если
l-ПсBи B_ПCB'тoт,t АB_ПCв.
Здесь l
и
B
-
МетaсимвoЛьl
(вспoмoгaтельI'ьle
симвoJlЬI' Ile вxo.цяrцliе
в aлфaвит);
l.B
_
кoнкaтеIraция BьIpa)кeний' oбoзнaчeнтrьlх
МеTaсиI\{BoJla}4и.
16' БAЗA: х
-
peryлярIloе
BЬIрax(rrrие
(PB).
PЕКУРCИjI:
a)
Если
Д
*
PB' то к Е*
_
PB.
b) Если
A_
PB и
,F'_ PB,
тo
tц EF
-PB.
с)Если Е_PB и l'_PB,тoи
(ЕvЛ)_PB'
Здeсь x
*
лrобoй сиМBoл из зa.цaннoгo алфaвитa;
t];
Е,
F
_
метaсиI\,t-
вольr; ,Е*
-
пoвTopeIIие BьIpa)кеIIиЯ
.Е
прoltзвoльHoе
Числo
paз
(в
тoм
uисле
и
ни
paзy);
Еl'_ конкaтeнaция;
(Д'v
Л)
-
вьIбop
одIIoгo из вьtpaжений.
l7.
БA3A: Пyстaя
цelloчкa
t
_
цепoчкa
нaд aлфавитoм
U.
PЕкУPCИJI:
Если l
_
цепо.rкa
нaД,
U
и
х
_
любoй
сlrмвoл из
U.
тo и Ах
-
цепoчкa
нaц U.
18.
Пpoстейtшие
фyнкции
Bсro.цy
oпpеДеленьt'
a oпеpaTopЬI
с}-IrеpIIo3и.
ции
и
IIpиМитивнoй
peкypсии
IIе
oгpaниЧивaroт
oблaстЬ
oпpе.це'гIеttия
фyнк-
ции.
l9. Пpoстейпraя
фyнкция.
20,
(a)
х*,
;
(б)
'
.'.
.
.'
.
(y
paз/
21.
(1)
B i1 лroбoe мaксиМaльEoe
IIo
BкJIючеIlи}o IIезaBplсиМoе мIlo)i(e-
ствo B любoм С с E
NIaксиI\{€IJIьII0 и IIo Чllслy, эJrrl\4rнТoв.
B .Д-1r мнoжeотвo
20
{a32}
мaксимaльIlo
пo вкJIIoЧениIсl
B зaдaннoм
пoДМIIo)кестве
B, нo не Мaк-
сllМaлЬно
Ilo числy
эЛеМеtlтoB.
(2)
Paнг
r
(B):2.
(3)
oбoлo'lкa
Sp
(B)
-
oбъединени€ эJIеМе}lтoB
втopoгo и
TреTьегo
стoлбцoвмaтpицьt
l.
(4)
Haпpимep,
{аn,
аzz\
-
цикл
в
l?. PaзyмееTся'
этo
цикst
и
в M.
(5)
Haпpимеp,
лIoбaЯ стpoкaL{aтpицЬI
А
-6aзуlc
M.
(6)
r
(Д')
:
3.
Этoт
рaЕг
сoвIIa.цaеT'
с
рallгoМ
6aзцca.
21
БиБЛ}IOгPAФиЧЕCI{ий
сIIисoк
1
. Hoвикoв
П.C. ЭлементЬI
мaтеМaтическoй
лoгики.
-
M.: Hayкa, l97].
_.
399 с.
2. Лaьpoв
И.A,,
Мaксимовa
JI.Л' ЗaДaчи
IIo
теopиlt I\4Ilo}кесTB, I\,iaтrlr{a-
тичеcкой
JIoгике
и TеоpиIl
aлгopитМoB.
_
М': Hayкa,
1984.
-22З
c'
3. Липский
B. Кoмбинaтopикa.цля
прo1pallМистoв.
-
М.: I\zIиp, i988.
-
210 c.
4' ЕIoвикoв
Ф'A.
ldискpeтнaя
МaТеМaтикa
для
пp0гpai\,tмI.Iотoв.
_
СП6.:
Питеp,2О02.
.30|
c.
5. ПaпaДимитpиy
Х., Стaйглltц
К. Кoмбинaтopн€lJl
oптиl\{изaцlrя. Aлго.
pитМЬI }1 слo}Iсtoсть.
_
М.:
Миp,
1985.
-
5l0 с.
6. Кapпoв
Ю.Г.
Теоpия
aвToМaToB.
_
СПб': Питеp, 2002.
-
2Q6 с,
22
oгЛABЛЕIIиЕ
L)
Учебное
издattие
PON4AI]OB
Bлaдиlrир
Федоpовин
N{,{ТЕI\4ATlIЧЕскAЯ
ЛoГИкA
и :ГЕoPИЯ AЛI.ОPи.гt!,tol}
Зaдaчrrик
Pедaктоp
Е.B. Невскas
Кoppектop
Е.B.
Aфaнaсьевa
Кoмпьrотеpнaя
веPстка Е.Г' Р:щченкo
ЛP
Ng 020275.
Пс,дписaнo
в печaTЬ 29,09.0з'
Фopмaт
60х84/16.
Бyмaгa
для
Mt{oжит'
техники. l'apпитyрa.Гaймс.
[lе.raть oфсетнaя.
Ус'п. пеv.
rr. 1,39.
У.r..из.ц. rI. 1,45. Tиparк 300 экз
зa""з
sl0.Д005t
Рeдaкционно-издaTeльcкий
кot'l11JIекс
Bлaдимпpскогo
ГoсyдapстBrнrloГо
ytIIlвсpс'{ТeТa.
600000'
Bлaдимиp,
yл.
Гoрькtlго' 87.