Wydział Techniki	Uniwersytet Śląski	Data
				26-01-1999
	Zakład Systemów Informatycznych
			Zadania z automatu skończonego.
Sprawozdanie numer 4.	Paweł Kopaczek	Ocena ...............
	Piotr Kopaczek	Podpis ..............

Zestaw nr 7.

Dla każdego zadania określić:

1. graf przejść

2. tablicę stanów automatu skończonego akceptującą określoną klasę słów

3. podać dwa przykłady ilustrujące pracę AS ( DAS lub NAS w zależności od zadania )

Należy w sprawozdaniach podać założenia ( np. z której strony czytane słowo ...).

Zad.1.

DAS akceptuje słowa, w których co drugi symbol jest symbolem b ( b może wystąpić jako pierwsze na 1,2 pozycji słowa ). Wśród symboli dowolnych może wystąpić również b.

DAS = ( Q, Σ, δ, q₀, F)

• Σ = {φ, a, b, c}

• Q, δ, q₀, F = ?

Zad.2.

DAS ma akceptować słowa, w których po d zawsze występują dwa symbole a.

DAS = ( Q, Σ, δ, q₀, F)

• Σ = {φ, a, b, c, d }

• Q, δ, q₀, F = ?

Zad.3.

DAS ma akceptować słowa, reprezentowane przez wyrażenie regularne:

w = ( a + c* )⁺ abcd(ccd⁺)^*

DAS = ( Q, Σ, δ, q₀, F )

• Σ = {φ, a, b, c, d }

• Q, δ, q₀, F = ?

Zad.4.

Skonstruuj NAS dla wyrażenia regularnego 01* + 1. Rozbij to wyrażenie na składowe i podaj kilka możliwości.

DAS = ( Q, Σ, δ, q₀, F)

• Σ = {φ, 0, 1 }

• Q, δ, q₀, F = ?

Zadanie 1.

< Q, Σ, δ, q_o, F>

gdzie:

Q - jest skończonym zbiorem stanów,

• Σ - jest skończonym alfabetem symboli wejściowych, q₀ należące do Q jest stanem początkowym od którego automat rozpoczyna działanie, Σ = {φ, a, b, c, d }

F⊆ Q - jest zbiorem stanów końcowych (stan akceptacji (A) lub nieakceptacji(N)),

δ - jest funkcją odwzorowującą Q x Σ w Q czyli δ określa każdemu stanowi q i każdemu symbolowi na wejściu nowy stan automatu.

Przykład:

Pojawienie się na wejściu słowa bbbabca spowoduje przejście automatu przez stany: q₀, q₂, q₁, q₂, q₁, q₂, q₁, N czyli słowo nie zostanie zaakceptowane, natomiast babcbc wymusi drogę: q₀, q₂, q₁, q₂, q₁, q₂, A czyli słowo zostanie zaakceptowane .

Zadanie 2.

< Q, Σ, δ, q_o, F>

gdzie:

Q - jest skończonym zbiorem stanów,

• Σ - jest skończonym alfabetem symboli wejściowych, q₀ należące do Q jest stanem początkowym od którego automat rozpoczyna działanie, Σ = {φ, a, b, c, d }

F⊆ Q - jest zbiorem stanów końcowych (stan akceptacji (A) lub nieakceptacji(N)),

δ - jest funkcją odwzorowującą Q x Σ w Q czyli δ określa każdemu stanowi q i każdemu symbolowi na wejściu nowy stan automatu.

Przykład:

Pojawienie się na wejściu słowa abcdaacdaa spowoduje przejście automatu przez stany: q₀, q₀, q₀, q₁, q₂, q₃, q₀, q₁, q₂, q₃, A czyli słowo zostanie zaakceptowane, natomiast babcbc wymusi drogę: q₀, q₀, q₁, q₂, q₃, q₀, q₁, q_2, N czyli słowo nie zostanie zaakceptowane .

Zadanie 3.

w = ( a + c* )⁺ abcd(ccd⁺)^*

< Q, Σ, δ, q_o, F>

gdzie:

Q - jest skończonym zbiorem stanów (q0 - q7),

• Σ - jest skończonym alfabetem symboli wejściowych, q₀ należące do Q jest stanem początkowym od którego automat rozpoczyna działanie, Σ = {φ, a, b, c, d }

F⊆ Q - jest zbiorem stanów końcowych (stan akceptacji (A) lub nieakceptacji (N)),

δ - jest funkcją odwzorowującą Q x Σ w Q czyli δ określa każdemu stanowi q i każdemu symbolowi na wejściu nowy stan automatu.

Przykład:

Pojawienie się na wejściu słowa accabcdccdd spowoduje przejście automatu przez stany: q₀, q₁, q₀, q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇, q₇, A czyli słowo zostanie zaakceptowane, natomiast caaabcacc wymusi drogę: q₀, q₀, q₁, q₀, q₁, q₂, q₃, N czyli słowo nie zostanie zaakceptowane .

Zadanie 4.

01* + 1

{0}

01* + 1

{ε}

{ε} {0} {ε} {1} {ε} {ε}

{ε}

{ε}

< Q, Σ, δ, q_o, F>

gdzie:

Q - jest skończonym zbiorem stanów

Σ - jest skończonym alfabetem symboli wejściowych, q₀ należące do Q jest stanem początkowym od którego automat rozpoczyna działanie, Σ = {φ, 0, 1 }

F⊆ Q - jest zbiorem stanów końcowych (stan akceptacji (A) lub nieakceptacji (N)),

δ - jest funkcją odwzorowującą Q x Σ w Q czyli δ określa każdemu stanowi q i każdemu symbolowi na wejściu nowy stan automatu.

Przykład:

Pojawienie się na wejściu słowa 0011 spowoduje przejście automatu przez stany:

q₀, A czyli słowo nie zostanie zaakceptowane, natomiast 0111 wymusi drogę:

q₀, q₁, q₁, q₁, A czyli słowo zostanie zaakceptowane .

6

Q₀

Q₁

Q₂

N

A

Q₀

{a, c}

{b}

b

START

φ

Q₀

START

Q₁

d

Q₂

a

Q₃

A

A

a

N

A

φ

φ

A

A

Q₁

Q₂

Q₃

Q₄

Q₅

Q₆

Q₇

A

A

START

N

A

A

A

Q₀

START

Q₁

{0}

{1}

{φ}

{1}

Q₀

Q₁

Q₂

Q₃

Q₄

Q₅

A

A

Q₆

Q₇

START

{1}

{ε}

N

A

---