Korean Automata in Java

State-Pattern을 이용하여 한글 오토마타 프로그램 만들어보기

오토마타란?

• 주어진 입력(문자 또는 기호로, 정해진 집합의 원소)에 의존해 작동하며, 유한한 상태의 집합을 갖고 있으고, 입력에 따라 현재 상태에서 정해진 다음 상태로 전이하는 수학적 기계이다.

• 위 그림은 오토마타의 간단한 예시이다.
  • 상태 : S1, S2
  • 입력값 : 0, 1
  • 전이 :
    • S1에서 0을 넣으면 S2로 전이
    • S1에서 1을 넣으면 S1로 전이
    • S2에서 0을 넣으면 S1로 전이
    • S2에서 1을 넣으면 S2로 전이

한글 오토마타란?

• 기본 개념
  • 키보드로 한글입력(자음, 모음)이 주어지면 주어지 자음고 모음을 훈민정음에 맞도록 결합하는 것이다. 영어와 같은 나열해서 쓰는 언어에는 없지만, 조합해서 쓰는 우리말의 경우 조합해야 한 글자로써으 의미를 가지기 때문에 이 기능이 필요하다.
  • 예를 들어 ㅎㅏㄴㄱㅜㄱ이 입력으로 주어지면, 출력값으로 한국을 출력해주는 것이다.
• 한글의 조합 방법 :
  • 자음 + 모음 = 가
  • 자음 + 모음 + 자음 = 각
  • 자음 + 모음 + 모음 = 과
  • 자음 + 모음 + 모음 + 자음 = 곽
  • 자음 + 모음 + 자음 + 자음 = 값
• 상태 : O, J, JM, JMJ, JMM, JMJJ, JMMJ
  • 한 글자를 조합하기 위한 상태를 말하며, 예를 들어 JM은 자음-모음 순서로 입력된 상태이다.
  • 따라서 한글 문장은 (o+jm+jmj+jmm+jmmj+jmjj)^*이라 할 수 있다.
• 입력값 : 자음은 j, 모음은 m, 기타문자는 o라 한다.
  • 단, ㅋㅋㅋ나 ㅠㅠㅠ같은 입력은 들어오지 않고, 한글에는 없는 문자인 ㅂ + ㄱ = ᄞ은 조합할 수 있다고 가정한다.
• 전이 :
  • 상태 O(Queue에 기타 문자가 들어와서 내보낸 상태)에서는 기타 문자가 Queue에 들어오면 들어온 문자를 바로 내보내고, 상태 O로 전이한다. 자음이 Queue에 들어오면 Enqueue하고, 상태 J로 전이한다. 모음이 Queue에 들어오면 잘못된 입력이다.
  • 상태 J(Queue에 자음만 들어온 상태, 예: ㄱ)에서는 기타 문자가 Queue에 들어오면 잘못된 입력이다. 자음이 Queue에 들어오면 잘못된 입력이다. 모음이 Queue에 들어오면 Enqueue하고, 상태 JM으로 전이한다.
  • 상태 JM(Queue에 자음-모음이 들어온 상태, 예: ㄱㅗ)에서는 기타 문자가 Queue에 들어오면 ‘자음-모음’을 합쳐서 내보내고, 기타 문자도 내보낸 뒤, 상태 O로 전이한다. 자음이 Queue에 들어오면 Enqueue하고, 상태 JMJ로 전이한다. 모음이 Queue에 들어오면 Enqueue하고, 상태 JMM으로 전이한다.
  • 상태 JMJ(Queue에 자음-모음-자음이 들어온 상태, 예: ㄱㅗㄱ)에서는 기타 문자가 Queue에 들어오면 ‘자음-모음-자음’을 합쳐서 내보내고, 기타 문자도 내보낸 뒤, 상태 O로 전이한다. 자음이 Queue에 들어오면 Enqueue하고, 상태 JMxJ로 전이한다. 모음이 Queue에 들어오면 ‘자음-모음’을 합쳐서 내보내고, ‘자음’이 남은 Queue에 Enqueue한 다음, 상태 JM으로 전이한다.
  • 상태 JMM(Queue에 자음-모음-모음이 들어온 상태, 예: ㄱㅗㅏ)에서는 기타 문자가 Queue에 들어오면 ‘자음-모음-자음’을 합쳐서 내보내고, 기타 문자도 내보낸 뒤, 상태 O로 전이한다. 자음이 Queue에 들어오면 Enqueue하고, 상태 JMxJ로 전이한다. 모음이 Queue에 들어오면 잘못된 입력이다.
  • 상태 JMxJ(Queue에 자음-모음-(자음 or 모음)-자음이 들어온 상태, 예: ㄱㅗxㄱ)에서는 기타 문자가 Queue에 들어오면 ‘자음-모음-x-자음’을 합쳐서 내보내고, 기타 문자도 내보낸 뒤, 상태 O로 전이한다. 자음이 Queue에 들어오면 ‘자음-모음-x-자음’을 합쳐서 내보내고, Enqueue한 다음, 상태 J로 전이한다. 모음이 Queue에 들어오면 ‘자음-모음-x’를 합쳐서 내보내고, ‘자음’이 남은 Queue에 Engueue한 다음, 상태 JM으로 전이한다.
    • JMxJ에서 x는 J(자음) 혹은 M(모음)을 의미한다.
• 조합된 문자를 출력하는 원리 :
  • 우선 입력된 문장을 큐에 넣고, 큐에서 조합을 마친 글자 단위로 출력을 한다.
  • 아래 표에서 out(n)은 큐에서 n개의 원소, 즉, n개의 char로 조합된 하나의 글자를 출력하는 연산이다.
  • 아래 표에서 push(c)는 문자 c를 큐에 넣는 연산이다.

	push(o)	push(j)	push(m)
O	O, out(1)	push(), J	ERROR
J	ERROR	ERROR	push(), JM
JM	O, out(2), out(1)	push(), JMJ	push(), JMM
JMJ	O, out(3), out(1)	push(), JMxJ	push(), out(2), JM
JMM	O, out(3), out(1)	push(), JMxJ	ERROR
JMxJ	O, out(4), out(1)	push(), out(4), J	push(), out(3), JM

프로젝트 구조

.
└── (package) hangleAutomata - Automata를 구성하기 위한 다양 한 기능들을 포함
    ├── HangleAutomataMain.java - 프로젝트의 main문
    ├── Automata.java - 오토마타의 요소를 정의
    ├── Elements.java - 한글의 자음과 모음을 각 영문자에 매칭
    ├── SentenceModel.java - input sentence의 구조 분석
    └── Utils.java - 어떠한 문자를 판별하여 그 결과를 반환
└── (package) state - Automata의 현재 상태 및 상태 의 전이와 관련된 것을 책임
    ├── State.java - 각 state에 polymorphism을 이용하기 위한 interface
    ├── OState.java
    ├── JState.java
    ├── JMState.java
    ├── JMJState.java
    ├── JMMState.java
    └── JMXJState.java

코드 소개

• 한글을 직접 입력하거나 출력하기엔 복잡한 문제가 있으므로, 영어 문자 하나에 한글 자 음과 모음을 하나씩 매칭시켜주었다.
• 매칭 방식은 가장 간단한 키보드에 적힌 대로(ㅁ은 a, ㄱ은 r) 해주었다.

자음	자음에 대응하는 영어	모음	모음에 대응하는 영어
ㄱ	r	ㅏ	k
ㄲ	R	ㅑ	i
ㄴ	s	ㅓ	j
ㄷ	e	ㅕ	u
ㄸ	E	ㅗ	h
ㄹ	f	ㅛ	y
ㅁ	a	ㅜ	n
ㅂ	q	ㅠ	b
ㅃ	Q	ㅡ	m
ㅅ	t	ㅣ	l
ㅆ	T	ㅐ	o
ㅇ	d	ㅒ	O
ㅈ	w	ㅔ	p
ㅉ	W	ㅖ	P
ㅊ	c
ㅋ	z
ㅌ	x
ㅍ	v
ㅎ	g

• 어떠한 상태에서 상태로 전이를 시키는 방법에는 조건문을 반복하는 방법과 state-pattern을 이용하는 방법이 있고, 여기서는 state-pattern을 사용하여 코드를 작성하였다.
• state-pattern을 사용한 이유는, 상태의 추가나 삭제가 용이하고, IF문의 반복보다는 가독성 높으 코드를 작성할 수 있다고 생각했기 때문이다.

코드

• HangleAutomataMain.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package hangleAutomata;

/**
 * @author msjo
 *
 */
public class HangleAutomataMain {
    public static void main(String[] args) {
        String s = "alstndml roqkf dlfwl - gksrmf dhxhakxk aksemfdjqhrl!" // 입력될 문장 : 민수의 개발 일지 - 한글 오토마타 만들어보기!
        SentenceModel sm = new SentenceModel(s);
        Automata a = new Automata(sm);
        
        a.charCombine(); // combine characters which construct a sentence
        System.out.println("[ Input ]");
        System.out.println(s); // shot input value
        System.out.println();
        System.out.println("[ Result ]");
        System.out.println(a.charCombineResult.toString()); // show result value
    }
}

• Automata.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package hangleAutomata;

import state.State;
import state.OState;
import state.JState;
import state.JMState;
import state.JMJState;
import state.JMMState;
import state.JMXJState;
/**
 * @author msjo
 *
 */
public class Automata {
    private SentenceModel sm = null; // class-instance which have sentence(inputed) and sentence's structure(consonant and vowel)
    public StringBuilder charCombineResult = null; // result about combine characters
    private boolean isErrorCase = false; // automata's current state == error(because of wrong input)
    private State state = null; // automata's state, when automata has processed current character processing

    public final State STATE_O = new OState(this);
    public final State STATE_J = new JState(this);
    public final State STATE_JM = new JMState(this);
    public final State STATE_JMJ = new JMJState(this);
    public final State STATE_JMM = new JMMState(this);
    public final State STATE_JMXJ = new JMXJState(this);

    public Automata(SentenceModel sm) { // Constructor
        this.sm = sm;
        this.charCombineResult = new StringBuilder();
        this.isErrorCase = false;
        this.state = STATE_O;
    }

    public State getEditState() {
        return this.state;
    }

    public void setEditState(State editState) {
        this.state = editState;
    }

    public void charCombine() { // algorithm, consonant and vowel combine to form letter
        for(int i = 0; i < this.sm.getSentence().length(); i++) {
            if(this.sm.getStructure().charAt(i) == Utils.CONSONANT) {
                this.state.inputConsonant(this.sm.getSentence().charAt(i));
            }
            else if(this.sm.getStructure().charAt(i) == Utils.VOWEL) {
                this.state.intputVowel(this.sm.getSentence().charAt(i));
            }
            else if(this.sm.getStructure().charAt(i) == Utils.OTHERS) {
                this.state.inputOthers(this.sm.getSentence().charAt(i));
            }
        }

        if((this.state != STATE_O) && (!this.isErrorCase)) { // if automata's final-state != STATE_O
            this.charCombineResult.append(Utils.BREAKPOINT); // add '|' at the end of result
        }
    }
    
    public void errorOccur() { // if error(wrong input) occur
        this.charCombineResult.replace(0, this.charCombineResult.length(), "(ERROR) Sentence contains characters those are not combined.");
        this.isErrorCase = true;
    }
}

• Elements.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package hangleAutomata;

import java.util.ArrayList;
import java.util.Arrays;
/**
 * @author msjo
 *
 */
public class Elements {
    private static final ArrayList<Character> CONSONANT = new ArrayList<Character>(Arrays.asList( // consonant list
            'r', /* ㄱ */
            's', /* ㄴ */
            'e', /* ㄷ */
            'f', /* ㄹ */
            'a', /* ㅁ */
            'q', /* ㅂ */
            't', /* ㅅ */
            'd', /* ㅇ */
            'w', /* ㅈ */
            'c', /* ㅊ */
            'z', /* ㅋ */
            'x', /* ㅌ */
            'v', /* ㅍ */
            'g', /* ㅎ */
            'R', /* ㄲ */
            'E', /* ㄸ */
            'Q', /* ㅃ */
            'T', /* ㅆ */
            'W'  /* ㅉ */
            ));
    private static final ArrayList<Character> VOWEL = new ArrayList<Character>(Arrays.asList( // vowel list
            'k', /* ㅏ */
            'i', /* ㅑ */
            'j', /* ㅓ */
            'u', /* ㅕ */
            'h', /* ㅗ */
            'y', /* ㅛ */
            'n', /* ㅜ */
            'b', /* ㅠ */
            'm', /* ㅡ */
            'l', /* ㅣ */
            'o', /* ㅐ */
            'p', /* ㅔ */
            'O', /* ㅒ */
            'P'  /* ㅖ */
            ));

    public static ArrayList<Character> getConsonant() {
        return CONSONANT;
    }

    public static ArrayList<Character> getVowel() {
        return VOWEL;
    }
}

• SentenceModel.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package hangleAutomata;

/**
 * @author msjo
 *
 */
public class SentenceModel {
    private StringBuilder sentence; // inputed sentence
    private StringBuilder structure; // structure of characters which compose of sentence(consonant, vowel, etc)

    public SentenceModel(String s) { // Constructor
        setSentence(s);
        setStructure(s);
    }

    public String getSentence() {
        return sentence.toString();
    }

    private void setSentence(String s) {
        this.sentence = new StringBuilder(s);
    }

    public String getStructure() {
        return structure.toString();
    }

    private void setStructure(String s) {
        String structure = Utils.whatIsThisStringStructure(s); // analysis of characters in sentence
        this.structure = new StringBuilder(structure);
    }
}

• Utils.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package hangleAutomata;

/**
 * @author msjo
 *
 */
public class Utils {
    public static final char CONSONANT = 'J';
    public static final char VOWEL = 'M';
    public static final char OTHERS = 'O';
    public static final char BREAKPOINT = '|'; // break between letters

    private static boolean isConsonant(char c) {
        for(char j : Elements.getConsonant()) {
            if(c == j) {
                return true;
            }
        }
        return false;
    }

    private static boolean isVowel(char c) {
        for(char m : Elements.getVowel()) {
            if(c == m) {
                return true;
            }
        }
        return false;
    }

    private static char whatIsThisChar(char c) { // analysis a character
        if(isConsonant(c)) {
            return CONSONANT;
        }
        else if(isVowel(c)) {
            return VOWEL;
        }
        else { // other characters
            return OTHERS;
        }
    }

    public static String whatIsThisStringStructure(String s) { // analysis a sentence(many characters)
        StringBuilder result = new StringBuilder();
        for(char c : s.toCharArray()) {
            result.append(whatIsThisChar(c)); // append 'J' or 'M' or 'O'
        }
        return result.toString();
    }
}

• State.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package state;

/**
 * @author msjo
 *
 */
public interface State {
    public static final int O = 0;
    public static final int J = 1;
    public static final int JM = 2;
    public static final int JMJ = 3;
    public static final int JMM = 4;
    public static final int JMXJ = 5;

    public int getStateType(); // get current state
    public void inputOthers(char c); // in current state, input other character
    public void inputConsonant(char c); // in current state, input consonant
    public void intputVowel(char c); // in current state, input vowel
}

• OState.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package state;

import hangleAutomata.Automata;
import hangleAutomata.Utils;
/**
 * @author msjo
 *
 */
public class OState implements State {
    Automata a = null;

    public OState(Automata a) {
        this.a = a;
    }

    @Override
    public int getStateType() {
        return State.O;
    }

    @Override
    public void inputOthers(char c) {
        a.charCombineResult.append("" + c + Utils.BREAKPOINT); // combine 'O'
        a.setEditState(a.STATE_O); // goto O-State
    }

    @Override
    public void inputConsonant(char c) {
        a.charCombineResult.append(c); // enqueue J(consonant)
        a.setEditState(a.STATE_J); // goto J-State
    }

    @Override
    public void intputVowel(char c) {
        a.errorOccur(); // error(wrong input) occur
    }
}

• JState.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package state;

import hangleAutomata.Automata;
/**
 * @author msjo
 *
 */
public class JState implements State {
    Automata a = null;

    public JState(Automata a) {
        this.a = a;
    }

    @Override
    public int getStateType() {
        return State.J;
    }

    @Override
    public void inputOthers(char c) {
        a.errorOccur(); // error(wrong input) occur
    }

    @Override
    public void inputConsonant(char c) {
        a.errorOccur(); // error(wrong input) occur
    }

    @Override
    public void intputVowel(char c) {
        a.charCombineResult.append(c); // enqueue M(vowel)
        a.setEditState(a.STATE_JM); // goto JM-State
    }
}

• JMState.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package state;

import hangleAutomata.Automata;
import hangleAutomata.Utils;
/**
 * @author msjo
 *
 */
public class JMState implements State {
    Automata a = null;

    public JMState(Automata a) {
        this.a = a;
    }

    @Override
    public int getStateType() {
        return State.JM;
    }

    @Override
    public void inputOthers(char c) {
        a.charCombineResult.append(Utils.BREAKPOINT); // combine 'JM'
        a.charCombineResult.append("" + c + Utils.BREAKPOINT); // combine 'O'
        a.setEditState(a.STATE_O); // goto O-State
    }

    @Override
    public void inputConsonant(char c) {
        a.charCombineResult.append(c); // enqueue J(consonant)
        a.setEditState(a.STATE_JMJ); // goto JMJ-State
    }

    @Override
    public void intputVowel(char c) {
        a.charCombineResult.append(c); // enqueue M(vowel)
        a.setEditState(a.STATE_JMM); // goto JMM-State
    }
}

• JMJState.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package state;

import hangleAutomata.Automata;
import hangleAutomata.Utils;
/**
 * @author msjo
 *
 */
public class JMJState implements State {
    Automata a = null;

    public JMJState(Automata a) {
        this.a = a;
    }

    @Override
    public int getStateType() {
        return State.JMJ;
    }

    @Override
    public void inputOthers(char c) {
        a.charCombineResult.append(Utils.BREAKPOINT); // combine 'JMJ'
        a.charCombineResult.append("" + c + Utils.BREAKPOINT); // combine 'O'
        a.setEditState(a.STATE_O); // goto O-State
    }

    @Override
    public void inputConsonant(char c) {
        a.charCombineResult.append(c); // enqueue J(consonant)
        a.setEditState(a.STATE_JMXJ); // goto JMXJ-State
    }

    @Override
    public void intputVowel(char c) {
        a.charCombineResult.insert(a.charCombineResult.length() - 1, Utils.BREAKPOINT); // combine 'JM'
        a.charCombineResult.append(c); // enqueue M(vowel)
        a.setEditState(a.STATE_JM); // goto JM-State
    }
}

• JMMState.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package state;

import hangleAutomata.Automata;
import hangleAutomata.Utils;
/**
 * @author msjo
 *
 */
public class JMMState implements State {
    Automata a = null;

    public JMMState(Automata a) {
        this.a = a;
    }

    @Override
    public int getStateType() {
        return State.JMM;
    }

    @Override
    public void inputOthers(char c) {
        a.charCombineResult.append(Utils.BREAKPOINT); // combine 'JMM'
        a.charCombineResult.append("" + c + Utils.BREAKPOINT); // combine 'O'
        a.setEditState(a.STATE_O); // goto O-State
    }

    @Override
    public void inputConsonant(char c) {
        a.charCombineResult.append(c); // enqueue J(consonant)
        a.setEditState(a.STATE_JMXJ); // goto JMXJ-State
    }

    @Override
    public void intputVowel(char c) {
        a.errorOccur(); // error(wrong input) occur
    }
}

• JMXJState.java

/**
 * Created on 2018. 10. 05.
 * @author msjo -- hufs.ac.kr, Dept of CES
 */
package state;

import hangleAutomata.Automata;
import hangleAutomata.Utils;
/**
 * @author msjo
 *
 */
public class JMXJState implements State { // X is J or M
    Automata a = null;

    public JMXJState(Automata a) {
        this.a = a;
    }

    @Override
    public int getStateType() {
        return State.JMXJ;
    }

    @Override
    public void inputOthers(char c) {
        a.charCombineResult.append(Utils.BREAKPOINT); // combine 'JMxJ'
        a.charCombineResult.append("" + c + Utils.BREAKPOINT); // combine 'O'
        a.setEditState(a.STATE_O); // goto O-State
    }

    @Override
    public void inputConsonant(char c) {
        a.charCombineResult.append(Utils.BREAKPOINT); // combine 'JMxJ'
        a.charCombineResult.append(c); // enqueue J(consonant)
        a.setEditState(a.STATE_J); // goto J-State
    }

    @Override
    public void intputVowel(char c) {
        a.charCombineResult.insert(a.charCombineResult.length() - 1, Utils.BREAKPOINT); // combine 'JMx'
        a.charCombineResult.append(c); // enqueue M(vowel)
        a.setEditState(a.STATE_JM); // goto JM-State
    }
}

입력 데이터

alstndml roqkf dlfwl - gksrmf dhxhakxk aksemfdjqhrl!

출력 데이터

als|tn|dml| |ro|qkf| |dlf|wl| |-| |gks|rmf| |dh|xh|ak|xk| |aks|emf|dj|qh|rl|!|

Reference

• https://en.wikipedia.org/wiki/Automata_theory