봄수의 연구실

정규 언어, 정규 문법, 유한 오토마타의 동치 관계 전체 문법이 주어지면 문법으로 부터 토큰들을 분리해내고 이 토큰들을 정규 문법으로 표현 토큰에 대한 정규 문법을 정규 표현으로 표시. 이 정규 표현을 인식하는 인식기를 만들면 을 주면 언어가 주어지면, 이를 정규표현으로 변환 정규표현을 인식하는 NFA을 구성, NFA를 DFA로 변환, DFA를 최소화 하면 어휘 분석기 를 만들 수 있음 정규 문법, 정규 표현, 유한 오토마타의 관계가 서로 동치관계 임을 증명 정규문법 ⇒ 정규표현 정규표현 ⇒ 유한오토마타 유한 오토마타 ⇒ 정규문법 정규문법 ⇒ 정규표현으로변환 정규표현에의해서 정의된 문법G에 의해 생성 되는 언어 L(G)가 무엇인지를 알기 위해서는, 정규 문법을 정규 표현으로 변환 정규 문법을 계수(coe..

NFA와 DFA DFA와 NFA는 서로 동등하다 DFA보다 NFA가 언어의 구조를 쉽게 표현 NFA는 DFA보다 프로그램으로 구현하기 어려움 DFA는 NFA보다 프로그램으로 구현했을 경우에 효율면에서 훨씬 우수 일반적인 구현은 DFA로 해야 되는데 NFA가 언어의 구조를 쉽게 표현할 수 있기 때문에 서로가 변환이 필요하다 DFA의 상태수 최소화(state minimization) DFA를 이용하는 어휘 분석기의 상태 전이표의 크기를 줄임 기억공간을 적게 차지하도록 하고 또한 어휘분석 프로그램을 간단히 하는데 큰 도움 상태수를 최소화하는 방법 동치관계(equivalence relation)을 이용 상태수를 합침(state merge) [정의 3.22] 구별가능(distinguishable) [정의 3.23..

페이로드-공격 에이전트-좀비, 봇 페이로드 부류는 악성 소프트웨어가 컴퓨터나 감염된 시스템 네트워크 자원을 공격자가 사용하기 위해 전복 시킨다. 인터넷에 연결된 컴퓨터를 비밀리에 장악하고, 그 컴퓨터를 이용해 공격을 수행하고 관리한다. 봇 작성자를 추적하기 어렵다 보통 공격자는 봇넷을 형성해서 공격한다. 주로 무결성과 가용성을 공격한다 봇 활용 Distributed Denial-of-service Attack (DDoS) (분산 서비스 거부 공격) DDoS 공격은 엄청난 양의 요청 또는 트래픽으로 네트워크, 서비스 또는 웹 사이트를 압도하여 정상적인 기능을 방해하려는 시도입니다. 웹사이트의 서버를 여러 소스에서 유입되는 대량의 트래픽으로 압도하여 합법적인 사용자가 웹사이트에 액세스할 수 없도록 합니다. ..

프로그래밍 언어론 - 식과 제어문 표현식(Expression) 계산 표현의 기본 수단 연산자, 피연산자, 괄호, 함수 호출 등으로 구성 연산자(Operator) 피연산자가 하나인 단항 연산자 피연산자가 2개인 이항 연산자 C 기반 언어 삼항 연산자: (i%2) ? “홀수” : “짝수” 대부분의 프로그래밍 언어에서 이항 연산자는 피연산자 사이에 위치합니다: x + y LISP에서 연산자는 피연산자 앞에 위치합니다: (+ x y) 연산자 표기 방법 중위 표기법(infix notation) : 연산자가 피연산자들 사이에 위치하는 표기법 전위 표기법(prefix notation) 연산자가 피연산자들보다 앞에 위치하는 표기법 예) 함수 호출 표기 : add(1, mul(2, 3)) 후위 표기법(prefix not..

오토마타 오토마타는 디지털 컴퓨터의 추상적 모델이다. 그래서인지 입력 장치, 제어 장치, 출력 장치, 저장 장치로 이루어져 있다. 추가로, 일시 기억 장치(무한개의 기억소자 cell로 이루어짐), 제어 장치(유한 개의 내부 상태 중 하나의 상태를 항상 유지)도 있다 오토마타의 분류 기능적인 측면 : 인식기(accepter)와 변환기(transducer) 구분 인식기의 경우 입력된 결과에 대해 오토마타는 인식/기각(accept/reject) 등을 표시하는 이진 기호를 출력한다 언어 변환기는 주어진 입력에 대응하는 새로운 문자열을 출력한다 변환기에는 상태에 따른 출력을 내는 Moore 기계와 전이에 따른 출력을 내는 Mealy 기계 등이 있다. 결정적 오토마타 VS 비결정적 오토마타 구분 결정적/비결정적 오..

프로그래밍 언어론 - 데이터 타입 프로그램의 모든 데이터에는 데이터 타입(Type)이 있다 즉 데이터 타입은 그 타입의 변수가 가질 수 있는 값들의 집합이다. 데이터 타입의 종류 기본 데이터 타입 정수 타입, 부동 소수점 타입과 같이 해당 언어에서 기본적으로 제공 사용자 정의 데이터 타입 레코드 타입과 같이 기본 데이터 타입을 이용하여 사용자가 생성 정수 타입 주요 관심사항은 정수 값을 표현하는 데 사용하는 바이트 수 FORTRAN과 같은 언어는 한 가지 크기만을 제공 Java와 C와 같은 언어는 여러 가지 크기를 제공 오버 플로우 : 해당 타입이 제공하는 범위를 넘어서면 오버플로우가 발생한다 비부호 정수 타입 C나 C++에서 제공 0과 양의 정수만 표현하며, unsigned로 시작하는 타입 부동 소수점..

EBNF EBNF의 등장 이유는 BNF를 이용해서 표현하는데 어려움이 있기 때문이다 예를들어 식별자의 길이를 지정해 준 경우 아래와 같이 엄청난 가지 수의 생성 규칙이 생성 될 수 있기 때문이다 ::= | | | | | | | ... | ::= a | b | c | ··· | z ::= 0 | 1 | 2 | ··· | 9 이와 같이 BNF는 반복되는 부분을 표시하는데 어려움을 가지기 때문에, 반복되는 부분을 쉽게 표시하면서 BNF (Backus-Naur Form)로 표시하는 방법이 EBNF이다. EBNF 표기법 반복되는 부분을 BNF 표기법보다 읽기 쉽고 간결하게 표현 BNF 표기법의 세 가지 메타 기호에 반복을 나타내는 { }와 [ ]를 추가하여 사용 {a}는a가0번이상반복될수있다는것을의미 정규표현 a..

구문 도표 쉽게 이해할 수 있도록 문법을 도식화하는 방법입니다. 일반적으로 구문 도표는 사각형과 타원 그리고 이들 사이를 연결한 간선(edge)으로 구성 구문 도표를 그리는 방법 터미널 기호 : 원 논 터니멀 기호 사각형 생성 규칙 접속 : 터미널/논 터미널을 간선으로 이어 통해 표현 생성 규칙 선택 : 병렬 처리하는 그림으로 표현 생성 규칙 : 반복 위의 그림은 B → α* 를 표현한 것이다 루프 형태로 표기하면, N 번 이상 반복하는 것을 표현 가능하다 예제 : 구문 도표로 표현하기 다음 문법을 구문 도표로 표현하라 G = (V_N, VT, P, S) V_N ={A,B,C} VT = {a, (, ), b, c {, }} S=A P: A→a|(B) B → bC C → {c} 논터미널 기호인 A와 B를 ..

정규 문법의 연산 순서 정규 문법의 연산자 우선순위와 연산 과정을 살펴보자 핵심 개념 정규식의 연산자 우선 순위는 정규식을 평가할 때 작업 순서를 명확히 하기 위해 정의됩니다. 다음은 정규 표현식 연산자와 그 우선 순위입니다 Kleene Star (*): 이 연산자는 우선 순위가 가장 높습니다. 바로 앞의 정규 표현식이 0개 이상 발생함을 나타냅니다. "r"이 정규식인 경우 "r*"는 0개 이상의 “r” 항목과 일치합니다. 연결(.): 두 번째로 높은 우선 순위는 연결 연산자입니다. 두 개의 정규식 "r"과 "s"를 하나로 결합합니다. 여기서 “r” 바로 뒤에 "s"가 옵니다. 즉, "r"과 "s"가 정규 표현식인 경우 "r.s"는 두 부분으로 분해될 수 있는 모든 문자열과 일치합니다. 여기서 첫 번째 ..

SSH SSH(Secure Shell)는 클라이언트-서버 모델을 사용하여 한 컴퓨터에서 다른 컴퓨터로 보안 원격 로그인을 위한 프로토콜입니다. SSSH 클라이언트/서버 응용은 대부분의 운영체제에서 광범위하게 수용됩니다 SSH 프토토콜 스택 SSH 프로토콜 스택의 구성은 크게 3가지로 나뉜다 전송 계층 프로토콜(Transport Layer Protocol) 전방향 기밀(즉 한 세션에서 세션 키나 영구 개인키가 손상되더라도, 이전 세션의 기밀성에 영향을 미치지 않는다)을 만족하는 서버 인증, 데이터 기밀성과 데이터 무결성을 제공한다 전송 계층에서는 옵션으로 압축도 가능하다 사용자 인증 프로토콜(User Authentication Protocol) 서버에게 사용자를 인증한다 연결 프로토콜(Connection ..