[Automata] Automata Definitions: Yield Definition

Automata Definitions: Yield Definition

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

 

# Automata Definitions

Definitions을 한다고 했을 때 Tree sturcture를 활용하거나 Finite Automata를 활용해서 정의가 가능하다.

이러한 정의가 이루어지기 위해서 기본적으로 정의되어야 할 것들이 있다.

• Concepts being defined
• Concepts used
• Logical symbols
• Important variables
• Tree structure for yields definition

이 5가지를 알아야 그 다음 단계의 definition이 가능하다.

---

# Concepts being defined

Concept defined에 대해서 이전 포스트에서 살펴보았듯이 concept 자체를 정의하는 것을 의미한다.

Concept을 define하기 위해서는 yields in one step에 대해서 알아야 하며 결과적으로 yields 되는 것들과 denoted 과정이 들어간다면 denoted 되는 순서에 대해서 정의가 되어야 한다.

예를 들면 아래와 같이 정의가 가능하다.

• yields in one step ((q,w), (q', w'));
• ((q1, w1) ⊢M (q2, w2));
• yields ((q1, w1), (q2, w2));
• ((q1, w1) ⊢M* (q2, w2))

 

---

# Concept used

어떤 Concept을 사용하고 있는지를 알아야지 최종적인 정의가 가능하다.

Concept이라고 하면 Concept name과 parameter로 구성되어 있으며, input과 ouput 모두 concept에 해당한다.

따라서 concepts used를 정의하는 방법은 아래의 예시와 같다.

• configuration(q, w)
• equal between string: w1 = w2 where w1 and w2 are strings
• concatenation(o) of strings: concatenation(a, w'); aw'
• tuples
• a sequence of configuration(=tuple of configurations)
• yields in one step((q, w), (q', w'))

---

# Logical Symbols

Statement의 정의 요소 중 하나인 Logical symbols도 전체 definition에서 빠질 수 없다.

산술적 기호가 아닌 논리적 기호를 유의하며 사용해야 한다.

---

# Important variables

주요한 변수들 또한 정의를 해주어야 한다.

여기서는 denoted 된 변수들도 모두 작성해준다.

 

---

# Tree structure for yields definition

definition의 최종 단계로 앞서 확인한 내용을 토대로 Tree structure를 만들어 준다.

---