두번째 시간에 배운 내용은 DFA 결정적 유한 인식기이다. 개념은 그리 어렵지 않고, 그래프만 잘 그래면 된다.




Deterministic Finite Automata(DFA)


String 을 A Finite Automaton 에 넣어 문자를 인식하는 기계이다. 인식한다면 yes 결과를 보여준다. 

여기에서 Finite Automaton은 알고리즘이라고 볼 수도 있다. 





Define



(세번째 원소인 δ 는 Transition Function 이라고 부른다.)




Exercise

위의 정의만 본다면 이해하기 어렵다. 예제를 통해 알아보자. 



집합 M 안에 있는 원소는 차례대로 위의 정의와 대입시키면 된다. 

상태는 q1, q2, q3 가 있고, 입력하는 문자들은 0과 1로 이루어져 있다. 

세번째 원소의 정의는 아래 2개 인자를 받아 다음 상태로 가는것이 정해져있다는것을 보여준다.

시작지점은 q0, 끝나는 지점은 q1 이다. (끝나는 지점은 유일할 필요가 없기때문에 집합으로 표시해준다.)


위의 정의를 토대로 그래프를 그려보면 




이와 같은 형태로 나타나게 된다. 




여기에 0101 이라는 스트링을 넣어주자.


q0 -> q1 -> q0 -> q1 경로를 지나서 F인 q1 에 도달하게 되었다. 

따라서 0101 이라는 문자열은 우리가 정의해준 DFA가 인식할 수 있는 문자열임을 알 수 있다. 

그래프를 그리면 정의만 보았을 때보다 상당히 쉽게 이해할 수 있다. 






Transition Function (δ) 확장



위 규칙을 사용하여 δ*(q0, 011) 의 값을 알아보자. 예제에 사용했던 DFA에 대입해보자.



1.        δ*(q0, 011) = δ  (δ*  (q0,   01),  1)


                  .      = δ  (δ   (δ*   (q0,   0),  1),   1)


                  .      = δ  (δ  (δ   (δ*   (q0,   λ),   0),   1),   1)




2.    간단히 정리

   

      δ  (δ  (δ   (δ*   (q0,   λ),   0,   1),   1)  =  δ  (δ  (δ   (q0,   0),   1),   1)

  

     δ  (δ  (δ   (q0,   0),   1),   1)  =  δ  (δ  (q0,   1),   1)


δ  (δ  (q0,   1),   1)  =  δ  (q1,   1) 


δ  (q1,   1)  = q2





'2016 > 형식언어와 오토마타' 카테고리의 다른 글

1. Languages and Grammars - 언어와 문법  (0) 2016.09.11

형식언어와 오토마타 첫시간은 언어와 문법에 대해서 배웠다.

여기서 언어와 문법은 컴퓨터 언어만 해당되는 것이 아니라 우리가 평소 사용하는 언어에도 해당될 수 있다.


Symbol(심볼) - 어떤것이든 상관 없다. 기호들의 집합




Alphabet(알파벳) - 심볼들의 집합, 유한하다.

ex) {0, 1} , {a, b, c, ..., z} -알파벳, 아스키코드 등등




String(문자열) - 알파벳을 정의하면 알파벳의 원소를 결합하여 문장을 만들어 낼 수 있다.


Notice






Language - '의미가 있는' 문장들의 집합 (L 은 길이가 0 이상인 문자열의 집합에 포함된다.)


Notice




Grammar -

정의 - 그래머 G = (V, T, S, P)

V = 변수들 (또는 non- terminal symbol)의 집합


T =  더이상 바꿀 수 없는 Symbol (ex 알파벳 a, b ...)


S = 시작하는 Symbol 


P = 생성규칙 - 변수, non - terminal symbol 로 부터 문장을 유도하는 규칙

        x -> y  = x를 y 로 바꿀 수 있다.

  이 규칙을 사용하여

       w 를 uxv 라 정의하고, z를 uyv 라 정의하면 w => z 가 된다. 

       W =>*Wn : 여러번 적용 iff (w1 => w2 => w3 => ...)



example 


    G = ( {S} ,  {a, b} ,  S ,  P )

S -> aSb .... 1번 규칙

S -> λ .... 2번 규칙



S =>* aabb




S =>    aSb    =>    aaSbb   =>    aaλbb   =>    aabb

                                   1번 규칙      1번 규칙       2번 규칙

 

'2016 > 형식언어와 오토마타' 카테고리의 다른 글

2. Deterministic Finite Automata(DFA) - 결정적 유한 오토마타(인식기)  (2) 2016.09.15

객체지향 수업 실습1일차

배운 내용 - 기본 문법(반복문), 자료형, 기본 입출력


 for 문이나 switch 와 같은 문법들은 c 언어와 매우 유사한 구조를 가지고 있어 내용에서 제외하였습니다. 





1. 문자열 입력과 출력




c언어 에서 처음배웠던 문자열의 입력함수는 scanf( ), 출력함수는 printf( ) 였다.

java 도 scanf() 와 printf() 처럼 문자열의 입력과 출력을 담당하는 명령이 있는데, 

바로 System.out.println(출력) 과 System.in(입력) 이다. 



2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
 
public class practice_java {
    public static void main (String args[]){
        String message;
        Scanner scan = new Scanner(System.in);
        
        System.out.println("메세지를 입력해 주시오");
        
        message = scan.nextLine();
        
        System.out.println("message : " + message);
        
        int num;
        Scanner scan2 = new Scanner(System.in);
        
        System.out.println("정수를 입력해 주시오");
        num = scan2.nextInt();
        
        System.out.println("num :" + num);
    }
}
cs






1. 우선 입력을 받아주려면 Scanner 클래스를 import 해주어야 한다.


   Scanner 클래스는 아래 api사이트에 잘 설명되어있다.

   (https://docs.oracle.com/javase/7/docs/api/)






2. scan 이라는 키보드로 부터 문자열을 입력받는 클래스를 새로 만들어준다. 

   Scanner 는 System.in 으로부터 받아온 문자열을 처리해준다


. 





3. String 형의 message 변수에 입력받은 문자를 입력해준다.

    scan.nextLine() 은 받아들인 문자열의 라인을 읽어온다.







4. message 에 입력한 문자를 출력한다.

   System.out.println() - 출력을 담당한다. + 는 문자열과 문자열을 이어준다.





5 결과







2. 주의사항


입력받은 문자를 변수에 저장해줄 때 입력받은 문자열과 저장해준 문자열의 자료형이 일치해야 한다. 

ex) int -> nextInt / double -> nextDouble / string -> nextLine ...


일치하지 않을 경우 에러가 난다. 


변수의 자료형 : int 

scan 으로 읽어온 자료형 : double (nextDouble로 읽어옴)



결과



커널


커널이란 운영체제의 정체정이라고도 말한다. 우분투, 페도라, Centos 등등 엄청 많은 운영체제가 같은 리눅스 계열로 묶이는 이유도 이들이 리눅스 커널을 사용하기 때문이다. 

  커널은 운영체제 맨 하부에서 돌아가며, 소프트웨어 로부터 요청받은 일을 하드웨어로 넘겨주는 역할을 한다. 따라서 커널이 날라가면 해당 os 는 사용하지 못하게 된다.  


커널의 종류는 모놀리식 커널, 마이크로 커널, 하이브리드 커널, 엑소 커널 등등 많이 있지만, 리눅스가 모놀리식 커널 방식을 사용하기 때문에 앞으로는 모놀리식 커널 위주로 공부하게 될 것이다. (윈도우는 NT 계열은 하이브리드 커널방식을 사용한다.)


위키백과

나무위키

http://egloos.zum.com/dstein/v/2172464



커널 개념도





+ Recent posts

티스토리툴바