본문 바로가기

분류 전체보기

 (79)
[계산이론] Properties of Regular Languages - 2 Lecture3 실습문제 주어진 정규 표현식에 대한 DFA를 찾고, 그 후에 정규 문법을 추출하라. solution Identifying non-regular languages ( 정규 아닌 언어 파악하기) 정규 아닌 언어들 정규 아닌 언어들은 유한 오토마타로 인식될 수 없다. 주장: 𝐿 = 0^𝑛1^𝑛 (𝑛 ≥ 0)은 정규가 아니다. 이 정규 언어라면 L에 대한 DFA를 구성할 수 있어야 한다. 그러나 DFA는 제한된 임시 저장 공간을 가지고 있으므로 n를 기억할 수 없다. 비둘기집 원칙 만약 𝑛마리의 비둘기가 𝑚개의 비둘기집에 위치한다면, 하나의 비둘기집에는 적어도 𝑛/𝑚마리의 비둘기가 있을 것이다. 만약 우리가 𝑛개의 물체를 𝑚개의 상자에 넣고 𝑛 > 𝑚이면, 적어도 하나의 상자는 그 안에 두 개 ..
[계산이론] Properties of Regular Languages - 1 렉쳐 3 실습 문제 주어진 정규 표현식에 대한 DFA(결정적 유한 오토마타)를 찾고, 그 후 정규 문법을 추출하라. Closure properties of regular languages ( 정규 언어의 폐포 속성) 정규 언어에 연산(operation)을 수행하면 어떤 일이 발생하는가 예를 들어, 두 정규 언어 𝐿1과 𝐿2가 주어졌을 때: 그들의 합집합도 정규인가?" "예 정규 언어는 합집합(union)에 대해 폐쇄(closed)되어 있다. 만약 𝐿1과 𝐿2가 정규 언어라면, 아래도 모두 정규 언어이다: 만약 𝑳1과 𝑳2가 정규 언어라면, 𝑳1 ∪ 𝑳2도 그렇다. 𝑟1과 𝑟2는 정규 표현식이라고 가정하면, 𝐿 𝑟1 = 𝐿1 그리고 𝐿 𝑟2 = 𝐿2 이다. 𝐿 𝑟1 ∪ 𝐿 𝑟2 = 𝐿(𝑟1 + 𝑟2) 임을..
[계산이론] Regular Languages and Regular Grammars - 4 Regular Grammars 정규 문법은 특정(certain) 형태의 생성 규칙을 사용하여 정규 언어를 정의합니다. 오른쪽 선형 (Right-Linear) grammars 과 왼쪽 선형 (Left-Linear) grammars 문법 G = (V, T, S, P)는 모든 생성 규칙이 다음 형태를 가질 때 오른쪽 선형 (Right-Linear) 이라고 합니다: 𝐴→𝑥𝐵 𝐴→𝑥 여기서 𝐴와 𝐵는 변수 V의 원소 (𝐴,𝐵 ∈ 𝑉) 이며, 𝑥는 터미널 문자열 T의 원소 ( 𝑥 ∈ 𝑇* )입니다. 문법 G = (V, T, S, P)는 모든 생성 규칙이 다음 형태를 가질 때 왼쪽 선형 (Left-Linear) 이라고 합니다: 𝐴→𝐵𝑥 𝐴→𝑥 여기서도 𝐴와 𝐵는 변수이며, 𝑥는 터미널 문자열입니다. 정규 문법은 오른..
[계산이론] Regular Languages and Regular Grammars - 3 DFA to regular expressions How can we extract regular expressions from a DFA? DFA에서 정규 표현식을 어떻게 추출(변환)할 수 있을까? 예시 해당 DFA는 𝑏*𝑎 (𝑎 +𝑏)* 라는 정규표현식으로 변환될 수 있다. 어떻게? 기본 개념 종료 상태 추가? 시작 상태 추가? 시작 과 종료 상태 사이에 새로운 상태 추가? Arden’s theorem (rule) 𝑃와 𝑄가 𝛴 위의 정규 표현식이라면, 𝑅 = 𝑄 + 𝑅𝑃 형태의 방정식은 𝑅 = 𝑄𝑃*의 유일한(unique) 해를 갖습니다. 예시 문제 1 𝐴 =𝐴𝑏+𝜆 ( ※ Considering incoming edges ) 𝐵 =𝐴𝑎+𝐵𝑎+𝐵 ( ※ Considering incoming edges ..
[계산이론] Regular Languages and Regular Grammars - 2 Regular expression and finite automata How can we represent regular expressions in finite automata? RE를 FA에서 어떻게 표현할 수 있는가? 𝐿(𝑎* + 𝑎* (𝑎 + 𝑏) 𝑐* ) 첫번째 방법 : 일반화된(Generalized) NFA , 통칭 ,GTG( Generalized Transition Graph ) 사용 기본적인 NFA는 전이(transition)를 나타내는 라벨로 알파벳 Σ의 구성원만을 사용합니다. 그러나 일반화된 NFA (또는 GTG)는 전이를 나타내는 라벨로 정규 표현식(Regular expressions)을 사용합니다. 이렇게 함으로써, 각 전이가 단순한 문자 대신 더 복잡한 문자열 패턴을 나타낼 수 있게..
[계산이론] Regular Languages and Regular Grammars - 1 Regular Expressions and Regular Grammars 오토마타를 사용하여 자연어를 이해하는 것은 어렵다. 자연어는 복잡하고 다양한 규칙과 예외 사항을 가지고 있기 때문입니다. 형식 언어 (formal language)는 이해가능하다!(understandable) 형식 언어는 언어의 특성(characteristic)을 일반화(generalize)하거나 추상화(abstract)하여 수학적으로 형식화(formalize)된 인공 언어(artificial language)입니다. 이러한 형식 언어는 자연어의 복잡성을 줄이고, 명확한 규칙과 구조를 가지므로, 오토마타와 같은 기계적 도구로 이해하고 분석하기가 더 쉽습니다. 예를 들어, 정규 언어(Regular language), 문맥 자유 언어(..
[계산이론] Finite Automata - 5 Reduction of the number of states One language can be accepted by many DFAs 하나의 DFA는 하나의 언어만 수용합니다 ( One DFA => One Language ) 결정적 유한 자동기 (DFA)는 명확하게 정의된 전이 함수를 가지고 있으므로 주어진 입력에 대해 항상 동일한 결과를 생성합니다. 따라서 각 DFA는 특정 언어를 수용하며, 그 언어는 DFA의 구조와 전이 함수에 의해 결정됩니다. 하나의 언어는 여러 DFA에 의해 수용될 수 있습니다 ( One language => many DFAs ) 특정 언어를 수용하는 DFA를 여러 가지 방식으로 설계할 수 있습니다. 예를 들어, 불필요한 상태를 가진 DFA와 최소화된 DFA는 동일한 언어를 수..
[계산이론] Finite Automata - 4 Equivalence of NFAs and DFAs Every NFA has an equivalent DFA?? Equivalence 두 finite automata M1과 M2가 동등하다(equivalent)고 말할 때, 그것은 𝐿(𝑀1) = 𝐿(𝑀2) 즉, 두 자동기가 동일한 언어를 수용한다는 것을 의미합니다. NFA (𝑁 = (𝑄, Σ, 𝛿, 𝑞0, 𝐹)) => DFA (𝑀 = (𝑄′, 𝛴, 𝛿′, 𝑞0′, 𝐹′)) NFA를 DFA로 변환하는 과정 1. 𝑁 에 대한 전이 테이블 생성 ( Create a transition table for 𝑁) 우선 N을 사용해 NFA에 대한 Transition Table을 만든다. 예시 NFA에 대한 Transition Table은 다음과 같다. 2. DFA의 시..

티스토리툴바