Arkusz zadań - zadania z automatów i języków formalnych przed kolokwium (tryb zaoczny)

Zadanie 1.

a)

Znajdź wyrażenia regularne i skonstruuj NAS-

Λ akceptujący podany język nad alfabetem ∑={a,b}:

{

}

4

2

:

*

<

≤

Σ

∈

=

A

A

L

{

}

3

)

(

:

*

=

Σ

∈

=

a

A

A

L

b)

L = { A

∈Σ

*

: w A występuje podsłowo b

3

}

c)
d)
e)

f)
g)
h)

Zadanie 2.

Zadanie 3.

Zadanie 4.

a)
b)

Zadanie 5.

a)

L = { A

∈Σ

*

: │A│jest liczbą nieparzystą i przyrostkiem A jest a }

L = { A

∈Σ

*

: na pozycji trzeciej znajduje się symbol a }

L = { A

∈Σ

*

: symbol a w słowie A występuje „trójkami” }

L = { A

∈Σ

*

: pierwszy i ostatni symbol w słowie A są identyczne }

L = { A

∈Σ

*

: A zawiera parzystą ilość podsłów ab }

Skonstruuj DAS akceptujący ten sam język, który jest akceptowany przez poniższy NAS-

Λ:

a)

b)

Znajdź wyrażenie regularne generujące ten sam język, który jest akceptowany przez poniższy NAS-

Λ:

a)

b)

Korzystając z lematu o pompowaniu pokaż, że następujące języki nie są regularne:

{

}

N

n

b

a

L

n

n

∈

=

+

:

3

4

{

}

n

m

b

a

L

m

n

≤

=

:

Sprowadź poniższe gramatyki do normalnej postaci Chomskiego i zbuduj automat ze stosem
akceptujący dany język.

{

} { }

{

}

)

,

,

,

,

,

,

,

,

(

S

bbY

Y

a

aX

X

XaY

S

b

a

Y

X

S

G

Λ

→

→

→

=

b)

{

} { }

{

}

)

,

,

,

,

,

,

,

,

(

S

b

bbbY

Y

b

a

X

XXY

S

b

a

Y

X

S

G

→

Λ

→

→

=

Zadanie 6.

a)
b)

Znajdź gramatykę opisującą język:

c)

d)

δ

a b Λ

s

0

{

s

1

}

∅

{

s

1,

s

2

}

s

1

∅

{

s

1,

s

2

}

∅

s

2

∅

∅

∅

δ

a b

Λ

s

0

{

s

0

s

2

} {

s

0

,

s

1

}

∅

s

1

∅

{

s

2

}

∅

s

2

{

s

1

}

∅

{

s

0

}

δ

a b Λ

s

0

{

s

1

} {

s

2

} {

s

1,

s

2

}

s

1

∅

{

s

1

s

2

}

∅

s

2

{

s

1

}

∅

∅

δ

a b

Λ

s

0

{

s

0

s

2

} {

s

0

,

s

1

}

∅

s

1

∅

{

s

2

}

∅

s

2

{

s

0,

s

1

}

∅

{

s

0

}

{

}

0

3

4

:

N

n

b

a

L

n

n

∈

=

+

{

}

3

)

(

:

*

=

Σ

∈

=

a

A

A

L

L = { A

∈Σ

*

: na pozycji trzeciej znajduje się symbol a }

L = { A

∈Σ

*

: pierwszy i ostatni symbol w słowie A są identyczne }

Czy którąś z tych gramatyk można zapisać w postaci regularnej ?