독학두비니

수학

finding x and p when we have successive large powers of an integer x, with modulo of prime p

그냥 심심해서 link : https://math.stackexchange.com/questions/1952453/finding-an-integer-x-and-a-3-digit-prime-p-that-solves-the-problem Finding an integer $x$ and a 3-digit prime $p$ that solves the problem $353, 46, 618, 30, 877, 235, 98, 24, 107, 188, 673$ are successive large powers of an integer $x$ modulo a 3-digit prime $p$. Find $x$ and $p$. This question seems impossible to me, I have tried m..

수학

Context-Free Language and Grammar

1. Context-Free Grammar A context free grammar is a quadruple G=(V,T,S,P) where –V: a finite set variables (or non-terminals) –T: a finite set of terminals –S: the start symbol Î V –P: a finite set of productions V → (VUT)* 기본적으로 context-free grammar는 형식 자체는 Regular Grammar와 같지만, production rule에 해당하는 부분만 다릅니다. 다시 기억해보면, regular language는 right-linear language와 left-linear language만 취급합니다. Conte..

수학

Pumping Lemma for Regular Languages

1. Pumping Lemma Pumping Lemma는 Regular Language의 일반적인 성질을 기술한 이론입니다. 따라서 어떤 language가 regular language를 판단할 때 사용됩니다. 참고로 한가지 써놓자면, pumping lemma는 언어가 non-finite일때를 한정해서 non-regular 증명용으로 사용합니다. 이에 대한 설명을 몇가지 덧붙이자면,1. 만약 어떤 language가 finite(유한)하다면 무조건 regular합니다. 그에 해당하는 FSM이 무조건 존재하기 때문이죠.2. 그러나 language의 길이가 non-finite(무한)한 경우, 이건 해당하는 FSM이 존재하지 않을지도 모릅니다. 따라서 이 경우에는 regular language가 아니라는 것을 ..

수학

Grammar의 정의와 Regular Grammar

0. Chompsky Hierchy Grammar, 즉 문법이라고 함은(평소에 우리가 쓰는 단어) 어떤 언어에 대해서 정해져 있는 규칙들을 모아 문법이라고 칭합니다. 그렇다면 regular grammar, 특히 계산이론에서의 regular grammar는 컴퓨터 언어에 있어서의 문법을 이야기합니다. 특히 컴퓨터 언어에서의 grammar를 제안한 사람은 바로 Noam Chompsky입니다. 총 4가지의 grammar를 제시했는데, 보도록 합시다. Grammar Type Grammar Accepted Language Accepted Automaton TYPE-0 Unrestricted Grammar Recursively Enumerable Language Turing Machine TYPE-1 Context..

수학

DFA 문제 팁

보호되어 있는 글입니다.

수학

DFA / NFA / Language 개념정리

개념정리를 해봅시다 1. DFA (Deterministic finite Accepter/Automata) dfa는 5개로 이루어진 튜플로 정의됩니다. M = (Q, ∑, 𝛿, q0 , F), where Q is a finite state of internal states, ∑ is a finite set of symbols called the input alphabet, 𝛿 : Q x ∑ → Q is a total function called the transition function, q0∈ Q is the initial state, F ⊆ Q is a set of final states. 설명 1. Q는 존재하는 모든 state를 모아놓은 것입니다. 2. ∑는 transition으로 가능한 모든 문자..

수학

Finite Automata to Regular Expression : 두가지 방법으로

Finite Automata to Regular Expression 두 가지 방법으로 이산수학이나 계산이론 등을 배우면, NFA를 DFA로, FA를 RE로 등등 형태변환이 항상 일어납니다. (제발 그만바꿔ㅠㅠ) 오늘은 FA를 RE로 바꾸는 과정을 알아볼건데, GNFA를 통해서 변환하거나, Arden's Rule을 활용하는 방법이 있습니다. 각 방법을 예시를 통해서 알아보도록 합시다. 고고 1. GNFA 이용하기 - GNFA 잠깐 소개 첫 번째 방법은 GNFA를 사용하는 방법입니다. GNFA에 대해서 모르신다구요????!!! dokhakdubini.tistory.com/449 GNFA에 대하여 GNFA에 대하여 Generalized NFA 오늘은 GNFA입니다. (하루에 다 써올리고 있지만) 1. GNFA..

수학

GNFA에 대하여

GNFA에 대하여 Generalized NFA 오늘은 GNFA입니다. (하루에 다 써올리고 있지만) 1. GNFA란 일단 GNFA는 Generalized Transition Graph(GTG)로도 불리우는 아이입니다. 기본적으로 GNFA는 Regular Expression의 표시를 가지고 있지만, NFA인 녀석이에요. 무슨 뜻이냐? NFA는 보통 transition을 표현할 때 하나의 기호(λ(람다)나 알파벳, 혹은 숫자)를 사용합니다. 그러나 GNFA는 그렇지 않고 Regular Expression처럼 일련의 기호를 사용합니다. 아래 보여지는 예시처럼요! 아무튼 GNFA는 NFA와 Regular Expression의 그 어딘가에 있습니다. 그리고 당연히 NFA에는 무조건 대응하는 GNFA가 존재합니다...

수학

Non-Finite Automata to Deterministic Finite Automata

Non-Finite Automata to Deterministic Finite Automata NFA를 DFA로 바꾸기 수학은 왜이렇게 변환하는걸 좋아할까요? 아무튼 NFA를 DFA로 바꾸는 방법, 그리고 검산하는 방법을 맨날 까먹어서 글로 작성합니다. 누군가에게도 도움이 되길 일단 NFA와 DFA의 가장 큰 차이점은 DFA가 규제가 훨씬 더 많다는 것입니다. 따라서 NFA를 DFA로 바꾸기 위해서는 조건에 맞춰서 DFA로 모두 바꿔주면 됩니다. 그 전에 별 의미없는 증명을 먼저 합시다. Theorem : Every NFA has an equivalent DFA. 그냥 외우는 편이 좋을 듯 합니다. 어떤 임의의 NFA로 이런방식으로 DFA를 만들었더니, 와! 똑같잖아!의 맥락이라.. NFA To DFA ..

수학

Arden's Rule에 대하여

Arden's Rule에 대하여 오늘은 Arden's Rule에 대해서 알아보고, 직접 증명할 예정입니다. Arden's Rule은 주로 DFA를 RE로 바꿀 때 주로 쓰인다고 합니다. 이 rule을 사용할 때 두 가지 표현방법이 있는데, 개인적으로 너무 헷갈려서 미리 작성하고 시작합니다. 고고 0. What is Arden's Rule? 일단 Arden's Rule 자체에 대해서 알아봅시다. Arden's Rule에 대해서 간단히 알아봅시다. Arden's rule states that the set A*⋅B is the smallest language that is a solution for the set X in the linear equation X = AX+B. i.e) X = AX + B, t..

수학

Constructing Minimal DFA using Myhill-Nerode Theorem

Myhill-Nerode Theorem 하나의 Language에 있어서 그에 적합한 DFA는 많지만, 최소화된 상태의 DFA는 하나뿐입니다. 따라서 DFA를 최소화시키기 위한 다양한 이론들이 있는데, 오늘은 Myhill-Nerode Theorem에 대해서 공부하고, 적용시켜보려고 합니다. 1. 기본적인 DFA minimizing method DFA가 필요 이상으로 늘어나는 이유는 줄일 수 있는 states를 과도하게 늘려서입니다. 따라서 같은 입력과 같은 출력을 내뱉는 states들에 대해 "indistinguishable"하다라고 표현합니다. 기호로는 다음과 같이 표현할 수 있습니다. Two states, s and t, are equivalent if for all possible stings w, ..