Regular languages

A language L is regular iff it is the language accepted by some DFA. 어느 Deterministic finite automata 중 하나라도 그 language가 수렴하면 그 language를 regular하다고 할 수 있다.
regular language는 다양한 방법으로 표현될 수 있는데 그 중 regular expression을 자주 사용한다.
예시를 보자.

• $L_3 = \{w\vert w\, in\, \{0,1\}^* \, and \, w,$viewed as a binary integer is divisible by 23$\}$

그럼 regular하지 못한 language는 뭘까?
nonregular language의 예시부터 보자.

• $L_1=\{0^n1^n|n\ge1\}$
  이것만 보고 뭔 차이인가 싶다. 좀 더 나중에 배울 NFA(Non-deterministic Finite Automata)를 알면 조금 더 이해가 쉬울 수 있다. 지금 DFA에 대한 개념도 잘 안 잡혀 있지만 최대한 이해해보자. 우선 DFA로 나타내는데 0이 n개, 1이 n개일 때 final state로 가야한다. n이 랜덤인데 state를 몇 개로 하고 transition 화살표는 어떻게 해야 0이 n개 1이 n개 일 때만 final state로 가도록 DFA를 표현할 수 있을까 ? 결론만 말하면 불가능하다.
• $L_2=\{0^n1^m0^l|n>3, m>5,l>2\}$
  이건 regular일까 non-regular인지 판단할 수 있을까 ? 이건 regular이다. $Q_0$인 상태에서 input에 0이 들어오면 $Q_1$, 또 input이 0이면 $Q_2$, $Q_3$까지 만약 다른 입력이 들어오면 $Q_0$로 돌아가도록 한다. 그리고 $Q_3$에서 0을 받으면 $Q_3$에 머무르도록 만든다면 연속한 0이 몇개가 들어와도 DFA로 표현할 수 있다. 이제 $Q_3$에서 앞선 방식과 마찬가지로 1이 5번 이상, 0이 연속해서 2번 이상. 이런 식으로 DFA를 만들 수 있다.

명확하게 regular와 nonregular를 구분 짓는게 아직 어색하고 힘들지만 대강의 느낌을 알 수 있다.

Nondeterministic finite automata

DFA와 다르게 한 종류의 input으로 인해 여러 state가 될 수 있다.
$\epsilon$(입실론)이 input에 추가된다. $\delta(q,\epsilon)=\{q\}$가 기본이다. 즉 자기 자신의 state는 $\epsilon$을 통해 되돌아 온다. 물론 $\epsilon$을 통해 다른 state가 될 수 있다.

Language of an NFA

string w가 NFA에 의해 $\delta(q_0, w)$가 final state를 포함한다면 w를 NFA의 language라고 한다.