[계산이론] Finite Automata - 2

Regular Languages

 

안녕하세요?

네, 반갑습니다.

오늘은 regular languages에 대해서 알아보는 시간을 가져보겠습니다.

사실 지금 이 글을 쓰고 있는 저자가 알고 있는 languge라 함은, [한국어], [english], 그리고 약간의 일본어 정도가 전부입니다.

다만, regulation에 대해서는 조금 알고 있는 바가 있습니다.

주로 emotion regulation에 관한 것인데요,

이 개념은 주로 J.Gross의 이론을 기반으로 하여 발전해오고 있습니다. 

emotion regulation은 말그대로 '정서를 조절하는 매커니즘'에 대한 것입니다.

emotion regulation process라는 것은 크게 정서를 유발하는 사건이 발생하기 이전과 발생한 후에 나타나는 과정으로 나누어 이해해볼 수 있습니다.

총 5개의 과정을 거쳐 주된 process가 구분됩니다.

이해하기가 어려우신가요?

그렇다고 하더라도 최대한 이해해보려고 노력해보세요!

노력하다보면 이루어질 것입니다.

행운을 빌겠습니다.

그럼 다음 시간에 계속 ...

-to be continued-

 

Regular language

• 언어(Language) L은 다음 조건을 만족할 때 정규(regular) 언어로 불립니다
  • 𝐿 = 𝐿(M) 을 만족하는 DFA M이 존재한다.
  • 𝐿(M)은 DFA M에 의해 수용되는 문자열의 집합을 나타냅니다.
• 간단히 말하면, 어떤 언어가 정규 언어인지를 판단하는 기준은 해당 언어를 수용하는 DFA가 존재하는지 여부입니다. 만약 어떤 언어를 수용하는 DFA를 구성할 수 있다면, 그 언어는 정규 언어입니다. 반대로, 어떤 언어를 수용하는 DFA를 구성할 수 없다면, 그 언어는 정규 언어가 아닙니다.

 예제 문제 1

• 언어 𝐿 = {𝑎𝑤𝑎: 𝑤 ∈ {𝑎, 𝑏}^∗}이 regular하다는 것을 보여라(show)
  • 이 언어는 'a'로 시작하고 'a'로 끝나며, 그 사이에 'a'와 'b'로만 구성된 임의의 문자열 𝑤를 포함하는 문자열의 집합을 나타낸다.
  • 이를 증명하기 위해, 우리는 다음과 같은 DFA를 구성할 수 있습니다:
  • 상태: q0, q1, q2 (및 기타 상태가 있을 수 있음)
  • 전이:
    • q0에서 'a'를 입력으로 받으면 q1로 전이됩니다.
    • q1에서 'b'를 입력으로 받으면 q1 상태를 유지합니다.
    • q1에서 'a'를 입력으로 받으면 q2로 전이됩니다.
    • q2는 수락 상태입니다.
    • q2에서 'a'를 입력으로 받으면 q2 상태를 유지합니다.
    • q2에서 'b'를 입력으로 받으면 q1로 전이됩니다.
    •  

다만 시작 상태 q0에서 b를 입력받은 후에는 trap state로 넘어가야한다. 이는 언어 L에 포함되지 않기 때문이다. 그러니

•  

• 이러한 transtition graph를 그릴 수 있다.
• 따라서, 이 DFA는 'a'로 시작하고 'a'로 끝나는 모든 문자열을 수용한다.
• 이는 주어진 언어 𝐿의 정의와 일치하므로, 𝐿은 정규 언어임이 증명된다.

예제 문제 2

• Show that the language 𝐿 = {𝑎^ 𝑛 𝑏^ 𝑛 | 𝑛 ≥ 0} is regular
  • 언어 𝐿 = {𝑎^𝑛 𝑏^𝑛 | 𝑛 ≥ 0}이 정규 언어인지 확인하라는 문제입니다.
  • 이 언어를 수용하는 L = L(M)이 되도록하는 DFA M을 구성해야 한다.
  • 그러나 이것은 불가능하다!
    • 𝐿은 정규 언어가 아닙니다.
    • 이 강의의 후반부에서 이를 증명하는 방법을 배울 예정입니다.

실습 문제

• Show that the language 𝐿 = {𝑤: |𝑤| 𝑚𝑜𝑑 3 = 0} is regular (Σ = {𝑎, 𝑏})