정보과학회 논문지 C : 컴퓨팅의 실제
Current Result Document :
| 한글제목(Korean Title) |
정규 언어와 문맥 자유 언어 사이의 편집 거리 계산 |
| 영문제목(English Title) |
Computing the Edit Distance between a Regular Language and a Context-free Language |
| 저자(Author) |
고상기
한요섭
Sang-Ki Ko
Yo-Sub Han
|
| 원문수록처(Citation) |
VOL 18 NO. 06 PP. 0464 ~ 0468 (2012. 06) |
한글내용
(Korean Abstract) |
우리는 주어진 정규 언어와 문맥 자유 언어 사이의 편집 거리(edit distance)를 계산하는 알고리즘을 제안 한다. 편집 거리는 일반적으로 하나의 문자열을 다른 문자열로 변환할 때 필요한 최소한의 연산의 개수를 의미한다. 문자열 단위가 아닌 언어 단위에서의 편집 거리를 계산함으로써, 패턴 매칭(pattern matching)이나 파싱(parsing)을 위해 주어지는 정규 언어와 문맥 자유 언어 간의 유사도를 효율적으로 파악할 수 있다. |
영문내용
(English Abstract) |
We propose an algorithm for computing the edit distance between a regular language and a context-free language. The edit distance is generally defined as the smallest number of operations required to transform a string into the other. By computing the edit distance between two languages instead of strings, we estimate the similarity between a regular language and a context-free language, which are often used for pattern matching or parsing.
|
| 키워드(Keyword) |
정규 언어
문맥 자유 언어
편집 거리
유한 오토마타
내리누름 오토마타
Regular Language
Context-free Language
Finite Automata
Pushdown Automata
Edit Distance
|
| 파일첨부 |
PDF 다운로드
|
