Overview

• Identifying non-regular languages
  • pigeonhole principle
  • pumping lemma
• Desicion Properties
  • some important questions about automata

Identifying Non-Regular Languages

ex. is L = { $a^n b^n | n≥0$ } Regualar?

Method 1: Pigeonhole principle

definition: n objects in m holes, n>m, at least one pigeonhole have more than one item

IN DFA? state = pigeonhole, input string = pigeon

Method 2: Pumping Lemma

• definition: 어떤 Regular Language에 대해, L의 모든 string w에 대해, |w|≥p인 w=xyz로 분해 가능하게 만드는 p(pumping length)가 존재한다.

  • 이때 xyz는 다음 조건을 만족한다.

    

  즉 일정 길이 이상의 word를 분해할 수 있고, y는 여러번 반복되어도 L에 들어가 있다.

  DFA에 사이클을 만드는 충분히 긴(p이상) string이 존재하여, 사이클을 pump해도 상관이 없다는 뜻!

• pf)

  regular L이기 때문에 DFA 존재, state들 $q_0, q_1, …, q_n$

  take string $w \in L$ s.t. $|w|≥p = n+1$ 이러면 state는 n개 입력은 n+1이기 때문에 중복되는 state가 최소 1개 존재한다(by pigeonhole principle) → $q_0 q_i … q_r … q_r … q_f$

  그러면 $\hat{\delta} (q_0, x) = q_r$, $\hat{\delta} (q_r, y) = q_r, \hat{\delta} (q_r, z) = q_f$ 각각 존재 이때 $|xy| ≤n+1=p, |y|≥1$

  $\therefore$ $\hat{\delta} (q_0, xz) = q_f, \hat{\delta} (q_0, xyz) = q_f,$

  $~~~\hat{\delta} (q_0, xy^2 z) = q_f, \hat{\delta} (q_0, x y^i z ) = q_f$

• how to solve

  

Desicion Properties of RL

• membership problem: is string w in RL L?

  • let DFA A representing A, simulate A(w)

• emptiness problem: for RL, does the language contain any string at all?

  • for DFA, compute set of states
  • if at least one state is reachable, yes

• infiniteness problem: is language infinite?

  • for DFA with n states, if language contains any string of length n or more, then infinte(by pigeonhole)

  

• equivalence problem: RL L=M?

  • change into emptiness problem

  • for L→DFA with states Q, M→DFA with states R, Product DFA has QxR

    

    

• Containment Problem L $\subseteq$ M?