오토마타와 형식언어

이번 학기에 오토마타와 형식언어(Automata & Formal Language) 라는 강의를 수강하게 되었다. 컴퓨터공학을 복수전공 하려면 정말 많은 추가 학점을 들어야 하는데, 그 중 오토마타와 형식언어라는 수업에 흥미가 생겨 시작하게 되었다." 공개적으로 학습 "

이어서 유한 오토마타다 (Finite Automata).dfa M 이 승인할 수 있는 Language 는 아래와 같다.L (M )={w ∈ Σ∗ : δ∗ (q0,w) ∈ F }dfa 가 승인하지 못한다면?L (M )={w ∈ Σ∗ : δ∗ (q0,w) /∈ F } .확

이어서 유한 오토마타(3)이다. 조금만 더 있으면 DFA(Deterministic Finite Accepter)에 이어 NFA(Non-determininstic Finite Accepter)에 대해서도 배우게 된다. 우선 중간 정리가 조금 필요하다.1\. DFA는 다음

유한 오토마타를 다루는 마지막 게시글이 될 것 같다. 유한 오토마타와 더불어 "정규 언어(Regular Language)에 대해서도 좀 다루었다. 아무래도 문제 풀이 위주의 게시글이 될 것 같다.첫 번째 문제다.001을 제외한 모든 문자열을 승인하라니, 처음에는 많이

유한 오토마타 마지막 게시글은 아니게 됐다. 아직 다룰 것이 조금 남아서 몇 개만 더 적어보려고 한다. 아래 필기 내용부터 공유하고자 한다. 여기서는 중요한 몇 가지만 짚고 넘어가고자 한다. 위 NFA를 보면 중요한게, 각 상태들 (qo,q1,q2)에서는 보이지는

다음은 DFA와 NFA의 동치성에 대해서 공유하고자 한다.우선 필기부터 첨부한다.NFA와 DFA의 동치성에서 중요한 개념은, 어떤 언어(문법)에 대한 NFA가 있으면, 해당 NFA에 대한 DFA도 존재한다는 것이다. (반대도 마찬가지)DFA는 본질적으로 NFA의 한 제