თეორიული ინფორმატიკა - 1 - Finite Automata

დეტერმინისტული სასრული ავტომატები

საკითხავი მასალა 

1.1 Finite Automata (p. 31 – 47) 

(წიგნი: Introduction to the Theory of Computation (M. Sipser)) 

---

ძირითადი საკითხები:

A deterministic finite automaton M is a 5-tuple, (Q, Σ, δ, q₀, F), consisting of

• a finite set of states (Q)
• a finite set of input symbols called the alphabet (Σ)
• a transition function (δ : Q × Σ → Q)
• an initial or start state (q₀ ∈ Q)
• a set of accept states (F ⊆ Q)

If A is the set of all strings that machine M accepts, we say that A is the
language of machine M and write L(M) = A. We say that M recognizes A or
that M accepts A. Because the term accept has different meanings when we refer
to machines accepting strings and machines accepting languages, we prefer the
term recognize for languages in order to avoid confusion.


Let w = a₁a₂ ... a_n  be a string over the alphabet Σ. The automaton M accepts the string w if a sequence of states, r₀,r₁, ..., r_n  exists in Q with the following conditions:

1. r₀ = q₀
2. r_i+1 = δ(r_i, a_i+1), for i = 0, ..., n−1
3. r_n ∈ F.

In words, the first condition says that the machine starts in the start stateq0. The second condition says that given each character of string w, the machine will transition from state to state according to the transition function δ. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. We say that M recognizes language A if
A = {w | M accepts w}.

A language is called a regular language if some finite automaton
recognizes it.

Let A and B be languages. We define the regular operations union, concatenation, and star as follows.

• Union: A ∪ B = {x | x ∈ A or x ∈ B}
• Concatenation: A∘B = {xy | x ∈ A and y ∈ B}
• Star: A* = {x1x2....xk | k >= 0 and each xi ∈ A}

Star works by attaching any number of strings in A together to get a string in the new language.

If A1 and A2 are regular languages, so is A1 ∪ A2.
If A1 and A2 are regular languages then so is Al o A2.

---

ამოცანები 

1. კენტი პოზიციების შემოწმება 

ა) ააგეთ დეტერმინისტული სასრული ავტომატი (DFA) ანბანზე {0, 1}, რომლის მიღებული სიტყვები ყველა კენტ ინდექსიან პოზიციაზე 1-ს შეიცავენ. ლუწ ინდექსიან პოზიციებზე შეუძლიათ ნებისმიერი სიმბოლო (0 ან 1) ჰქონდეთ. 

ბ) ახლა ააგეთ DFA (იმავე ანბანით), რომლის მიღებული სიტყვები რომელიმე კენტ ინდექსიან პოზიციაზე მაინც შეიცავენ 1-ს. ლუწ ინდექსიან პოზიციებზე ისევ ნებისმიერი სიმბოლო შეიძლება გვქონდეს.

ა)

ბ) 

ორივე შემთხვევაში იგულისხმება, რომ პირველი შემომავალი სიმბოლო კენტ ინდექსზეა (ანუ ათვლას 1-იდან ვიწყებთ და არა 0-დან). ბ-ში q0 გადადის q1-ში თუ 0 შემოვიდა და უკან ვბრუნდებით თუ შემოვიდა ან 0 ან 1 (რატომღაც ცუდად დახატა).

2. ქვესტრინგი კონკრეტულ პოზიციებზე 

ა) ააგეთ DFA ანბანით {a, b}, რომელიც მიიღებს ყველა სიტყვას (და არცერთ სხვას), რომელიც შეიცავს ქვესტრინგს “aba”. 

ბ) ააგეთ DFA ანბანით {a, b}, რომელიც მიიღებს სიტყვებს, რომლებიც შეიცავენ სიმბოლო a-ს რომელიმე 4-ზე გაყოფადი ინდექსის მქონე პოზიციაზე. 

გ) ააგეთ DFA, რომელიც მიიღებს სიტყვებს, რომლებიც შეიცავენ ქვესტრინგ “aba”-ს რომელიმე 4-ზე გაყოფად ინდექსზე დაწყებულ პოზიციაზე. 

ა)

ბ)

გ)

3. სიტყვების მიღება სიგრძის მიხედვით

ააგეთ DFA, რომელიც რომელიღაც მოცემული რიცხვი n-სთვის მიიღებს: 

ა) ყველა ზუსტად n სიგრძის სიტყვას 

ბ) ყველა არანაკლებ n სიგრძის სიტყვას 

გ) ყველა არაუმეტეს n სიგრძის სიტყვას

4. დასაწყისის და ბოლოს შემოწმება 

ააგეთ DFA, რომელიც მიიღებს სიტყვებს, რომლებიც იწყება 0-ზე და მთავრდება 1-ზე. DFA-ს ანბანი {0, 1} უნდა იყოს.

5. ენების გაერთიანება და თანაკვეთა 

ა) ააგეთ DFA ანბანით {0, 1}, რომელიც მიიღებს ყველა სიტყვას, რომელსაც ან 0-ების რაოდენობა აქვს ლუწი ან 1-ების რაოდენობა – კენტი. 

ბ) ააგეთ DFA, რომელიც მიიღებს ენას L: 

L = {w | w შეიცავს მინიმუმ ორ 0-იანს და მინიმუმ სამ 1-იანს}

ა)

ბ)