ZADANIA
Języki formalne:
Zadanie 1.1
Niech
{ }
b
a,
=
Σ
,
{
}
2
,
,
ba
b
a
a
L
=
. Wska
ż słowa o długości 5 należące do języka
.
*
L
Zadanie 1.2
Niech
{ }
b
a,
=
Σ
,
{
}
{
}
1
:
,
2
:
*
2
1
=
Σ
∈
=
≤
=
x
x
L
k
ba
L
k
. Wyznacz wszystkie słowa
nale
żące do języka:
a)
2
1
L
L
+
b)
2
1
L
L
∩
c)
2
1
L
L
⋅
d)
2
1
\ L
L
Zadanie 1.3
Jakie relacje zachodz
ą między językami
*
2
*
1
i L
L
je
śli
a)
{
}
{
}
...
,
,
,
,
,
6
4
2
2
2
1
b
b
b
a
L
b
a
L
=
=
b)
{
}
{
}
Λ
=
=
,
,
,
,
3
2
2
1
a
a
L
a
a
L
c)
{
}
{
}
b
aba
a
L
ab
a
L
,
,
,
,
2
1
=
=
d)
{
}
{
}
ab
a
L
ba
a
L
,
,
,
2
1
=
=
Zadanie 1.4
Uzasadnij,
że nie są równe następujące języki:
a)
(
)
*
2
*
1
*
2
1
L
L
i
L
L
+
+
b)
(
)
*
2
*
1
*
2
1
L
L
i
L
L
⋅
⋅
Wyrażenia regularne:
Zadanie 1.5
Poka
ż, że słowa
a)
A = a
5
b)
B = b
5
c)
C = a
7
b
5
d)
D = b
8
a
4
b
2
nale
żą do języka
L((a
*
b)
*
a
*
)
. Opisz ten j
ęzyk.
Zadanie 1.6
Opisz j
ęzyki generowane przez następujące wyrażenia regularne
a)
A =
a
3
(a+b)
*
b
3
b)
B =
b
*
a
3
b
*
+
a
*
b
3
a
*
c)
C = (
(a+b)
3
)
*
d)
D = a
(
(a+b)
3
)
*
e)
E = b
*
(a+
Λ
Λ
Λ
Λ
) b
*
(a+
Λ
Λ
Λ
Λ
) b
*
(a+
Λ
Λ
Λ
Λ
) b
*
f)
F = (a+b)
*
a (a+b)
*
a (a+b)
*
Zadanie 1.7
Znajd
ź wyrażenia regularne opisujące języki nad alfabetem
Σ
={a,b}
a)
{
}
4
:
*
<
Σ
∈
=
A
A
L
b)
{
}
4
:
*
>
Σ
∈
=
A
A
L
c)
L={ A
∈Σ
*
: przedrostkiem A jest a i podsłowem A jest b
4
}
d)
L={ A
∈Σ
*
: przedrostkiem A jest a lub podsłowem A jest b
4
}
e)
( )
{
}
4
:
*
=
Σ
∈
=
a
A
A
L
f)
( )
{
}
a
A
A
L
4
:
*
Σ
∈
=
Automaty skończone:
Zadanie 1.8
Niech b
ędzie dany automat typu DAS M = ( Q ,∑, s
0
, F,
δ
), gdzie Q={s
0
,s
1
,s
2
,s
3
}, ∑={a,b},
F={s
1
,s
2
} oraz funkcja przej
ść
δ
dana za pomoc
ą tabelki:
δ
a
b
s
0
S
3
s
1
s
1
s
2
s
0
s
2
s
1
s
2
s
3
s
3
s
3
Znajd
ź
(
)
A
s ,
ˆ
0
δ
je
śli
a)
A
=baba
b)
A
=abba
c)
A= (ba)
2
b
3
d)
A=b(ab
2
)
3
Które z tych słów jest akceptowane przez automat M?
Zadanie 1.9
Niech b
ędzie dany automat typu NAS M = ( Q ,
Σ
, s
0
, F,
δ
) = ({s
0
,s
1
,s
2
,s
3
},{a,b}, s
0
, {s
1
},
δ
) ,
którego funkcja przej
ść jest opisana tabelą:
δ
a
b
s
0
{ s
2,
s
3
}
{s
1
}
s
1
{s
0
}
∅
s
2
{s
1
}
∅
s
3
{s
0
}
{s
3
}
Znajd
ź
(
)
A
s ,
ˆ
0
δ
je
śli
a)
A
=a
2
b
2
b)
A
=(ab)
2
c)
A=a
5
d)
A=a
4
b
Które z tych słów jest akceptowane przez automat M?
Zadanie 1.10
Niech b
ędzie dany automat typu NAS-Λ M = ( Q ,
Σ
, s
0
, F,
δ
) = ({s
0
,s
1
,s
2
,s
3
},{a,b}, s
0
, {s
4
},
δ
) ,
którego funkcja przej
ść jest opisana tabelą:
δ
a
b
Λ
s
0
{ s
1
}
{s
1
}
∅
s
1
{s
0
, s
2
,
s
3
}
∅
{s
3
}
s
2
{ s
2,
s
4
}
{s
4
}
∅
s
3
∅
{s
3
}
{s
4
}
s
4
∅
∅
∅
Znajd
ź
(
)
A
s ,
ˆ
0
δ
je
śli
a)
A
=(ba)
2
b)
A
=(ab)
2
c)
A=a
2
d)
A=b
2
Które ze słów jest akceptowane przez ten automat ?
Zadanie 1.11
Opisz j
ęzyki akceptowane przez następujące automaty określone za pomocą grafów (napisz również
odpowiednie wyra
żenia regularne):
a)
b)
c)
d)
e)
f)
Zadanie 1.12
Skonstruuj automaty NAS-
Λ akceptujące języki opisane w zadaniu 1.7
Zadanie 1.13
Skonstruuj automat NAS-
Λ akceptujący podany język nad alfabetem ∑={a,b}:
a)
L = { A
∈Σ
*
: przedostatnim symbolem w A jest a lub
│A│< 3 }
b)
L = { A
∈Σ
*
:
│A│jest liczbą parzystą lub przyrostkiem A jest a }
c)
{
}
2
)
(
1
)
(
:
*
=
∨
=
Σ
∈
=
b
A
a
A
A
L
d)
{
}
)
(
2
1
)
(
:
*
b
A
a
A
A
L
∧
=
Σ
∈
=
a
b
a
b
b
b
b
a
a
a
b
a
a
b
a,b
a,b
a,b
a,b
a,b
b
b
b
a,b
a
a
a
a
Λ
b
b
b
Zadanie 1.14
Jakie s
ą zależności między językami akceptowanymi przez poniższe automaty:
a)
b)
Zadanie 1.15
Skonstruuj automat DAS akceptuj
ący ten sam język, co poniższy automat NAS-Λ:
a)
b)
c)
d)
Λ
a
a
1
2
b
a,b
3
0
a,Λ
a
0
1
2
3
a,b
a,b
b
b
Λ
a
a
Λ
Λ
0
1
2
3
b
Λ
a
Λ
1
b
0
3
2
b
a
Λ
M
1
b
a
Λ
M
2
b
a
Λ
Λ
b
a
Λ
a
M
1
M
2
Twierdzenie Kleenego:
Zadanie 1.16
Metod
ą z dowodu Kleenego znajdź wyrażenie regularne generujące język akceptowany przez poniższy
automat
a)
b)
c)
d)
Zadanie 1.17
Metod
ą z dowodu Kleenego znajdź automat akceptujący język
a)
L( a(a+bb))
b)
L((a+bb)
*
)
c)
L( (a+bb)(bb)
*
)
d)
L(( (a+bb)
*
+ a(a+bb) + (bb(a+bb))
*
+ (a+bb)(bb)
*
)
*
)
Zastosowanie lematu o pompowaniu:
Zadanie 1.18
Korzystaj
ąc z lematu o pompowaniu pokaż, że następujące języki nie są regularne:
a)
{
}
N
n
b
a
L
n
n
∈
=
+
:
3
b)
{
}
N
n
a
b
a
L
n
n
n
∈
=
+
:
5
2
c)
{
}
N
n
m
n
m
b
a
L
m
n
∈
∧
<
=
,
:
d)
{
}
N
k
n
m
k
n
m
a
b
a
L
k
m
n
∈
∧
+
>
=
,
,
3
:
e)
DODAWANIE
f)
PALINDROMY
a
b
a
1
b
3
2
a
0
a
b
Λ
1
b
0
3
2
a
a
a
b
Λ
a,b
0
3
2
b
a
1
a
b
Λ
1
a,b
0
3
2
b
a
Wyszukiwarka
Podobne podstrony:
więcej podobnych podstron