튜링머신은 DFA, PDA와는 다른 또 새로운 오토마타다. 1. 읽기-쓰기 테이프(Read-write tape)를 갖는다. 테이프는 오른쪽으로 무한하다. 테이프의 초깃값은 입력 문자열로 채워져 있으며, 나머지는 blank(⊔)로 채워져있다.2. 최초에 헤드(Head)는 가장 왼쪽 셀(cell)을 가리키고 있다.3. 이제 오토마타는 매 전이마다 아래의 행동을 해야한다.→ 헤드를 오른쪽 혹은 왼쪽으로 움직인다.→ 심볼(symbol)의 값을 다른 심볼로 바꾸거나 그대로 둔다.→ 상태를 옮긴다. 튜링머신(TM)의 엄격한 정의(Formal Definition)$\text{TM is a 7-tuple}(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{rej..

":)" 문제가 있다고 생각해보자. ":)" 문제는 어떤 프로그램이 :)를 출력하는지 아닌지를 확인하는 문제다. 결론부터 말하자면, 컴퓨터는 이 단순한 문제를 항상 해결하지 못한다. 만약 이런 프로그램이 입력으로 들어온다면 문제의 정답을 "yes"라는걸 쉽게 알 수 있다.int main() { printf(":)");}하지만, 이런 문제라면 어떨까? 코드의 내용을 간단히 요약하자면, n을 입력받고, 가능한 모든 정수쌍 (x,y,z)를 순회하면서 $x^n+y^n=z^n$가 성립하면 ":)"를 출력하는 코드다. 가령 $n=2$라면, $3^2+4^2=5^2$에서 ":)"가 출력될 가능성이 있다.int main() { int n, tot, x, y; scanf("%d", &n); while(1) { ..

기본 정규 연산우리는 지금까지, 결정적/비결정적 유한 오토마타의 정의를 배웠다. 앞으로는 오토마타와 정규언어들의 속성들에 대해 다룰 것이다. 그 이전에, 이 속성들을 익히거나 증명하는데에 유용한 도구상자들을 준비했다. 아래의 3가지 연산은 정규 연산(regular operation)이라 불리는 기본적인 언어들 간의 연산이다. 어떤 언어 A,B에 대하여 아래처럼 정의된다. Kleene는 클레이니, 클리네 등으로 발음하는 듯 하다. 우리는 자연수 $\times$ 자연수가 자연수라는 사실을 알고 있다. 이것을 수학에서는 자연수가 곱셈에 대하여 닫혀있다(closed)고 말한다. 마찬가지로, 정규언어는 위 3가지 기본 정규 연산에 대하여 닫혀있다. 예를 들어, 정규언어와 정규언어의 union은 정규언어다. 달리 ..

카이스트 CS322 형식언어 및 오토마타 공부 내용입니다.정규언어1. 유한 결정적 오토마타(DFA, Deterministic Finite Automata)2. 유한 비결정적 오토마타(NFA, Non-deterministic Finite Automata)3. DFA와 NFA의 동등성4. 정규표현식과 NFA의 동등성5. Pumping Lemma6. 정규언어의 폐쇄성(Closure)과 동등성7. 정규언어의 최소화8. 마이힐-네로드 정리(Myhill-Nerode Theorem)9. Monadic Second-Order Logic(MSO) 문맥 자유 언어10. 문맥 자유 언어(Context Free Language) 11. 푸쉬다운 오토마타(PDA, Pushdown Automata)12. PDA와 CFG의 동등성..

Firebase Hosting에 도메인 주소를 추가했는데 아래와 같은 화면이 뜨면 당황스럽다.위 내용대로 3가지 가능성이 있다.1. 아직 배포를 안함(You haven't deployed an app yet)- 그렇지만 website-xxx.web.app 주소는 정상적으로 동작하고 있었기에, 이것은 배제할수 있었다.2. 빈 폴더를 배포함(You may have deployed an empty directory)- 역시 그럴리가 없다.3. 커스텀 도메인이지? 우리가 아직 설정을 덜 끝냄.(This is a custom domain, but we haven't finished setting it up yet.)- 무슨 설정을 덜 끝냈다는 걸까? 아마도 저 페이지는 서빙에 뭔가 문제가 있을 때 땜빵으로 서빙하..

정규표현식우리는 언어를 "1로 시작하는 문자열" 혹은 "1이 짝수번 들어가는 문자열" 등으로 주절주절 표현했다. 좀 더 편리하고, 수학적으로 표현하는 방법은 없을까? 앞서 배운 3가지 기본 연산, union, concatenation, Kleene star을 이용해서 표현할 수 있다. 어떤 정규표현식 R이 표현하는 언어는 $\mathcal{L}(R)$ 이라고 표기하고, 정규표현식 R의 언어(language of R)라고 부른다.{1이 딱 한 번 들어가는 문자열} = $\mathcal{L}(0^*10^*)${최소 1이 한 번 들어가는 문자열} = $\mathcal{L}(\{0,1\}^*1\{0,1\}^*)${짝수 길이의 문자열} = $\mathcal{L}((\Sigma\Sigma)^*)$ 이게 정규표현식이..

NFADFA의 전이함수 δ는 가능한 모든 상태와 알파벳에 대하여, 하나의 다음 상태를 반환한다고 했다. 이 특징은 DFA의 이름에 들어간 "Deterministic(결정적인)" 이라는 수식어에서도 알 수 있다. 반면 "Non"-deterministic한 유한 오토마타인 NFA(Nondeterministic Finite Automata)의 전이함수 δ는 반환값이 하나가 아닌 여러개이거나, 0개일수도 있다.위 diagram의, $q_0$에서 뻗어나오는 화살표를 보자. 0이라는 입력에 대해 두 개의 화살표로 뻗어나오고 있다. 반면 $q_1$의 경우, 0이라는 입력에 대해 어떤 뻗어나오는 화살표도 찾아볼 수 없다. 위 오토마타에 "00101"이라는 입력이 들어왔을 때를 생각해보자. 이제는 상태변화가 한 줄기가 ..

티스토리 글에서 수식을 입력하기 위해 MathJax를 이용하면 편리하다. 자바스크립트 MathJax 모듈 내 코드는 LaTeX 문법을 수식으로 변환해준다. 예를 들어 `1 \lt 2` 를 $ 1 \lt 2 $ 로 보이게끔 바꿔준다. 이 MathJax를 적용하는 방법은 구글링을 통해 쉽게 찾을 수 있다. 그리고 대다수의 블로그는 티스토리의 스킨 HTML의 태그 안에 아래의 그러나, 이 방법은 나에게 동작하지 않았다. 정확히는 매번 화면에 진입할때마다 수식이 제대로 보이기도 했고, 안 보이기도 했다. 그 이유는 티스토리가 글을 로딩하는 시점과 MathJax 모듈을 로딩하는 시점의 차이 때문으로 분석된다. 1. 티스토리 글이 MathJax 모듈보다 먼저 로딩(실행)될 경우- 티스토리 글 로딩 -> 로딩된 ..