CIDA Lab @ UoS

FAdo 라이브러리 사용 방법

       

실습 진행 시 어려운 점이 있으면 Piazza를 이용해 질문하세요.

       

조교: 김수현(tngus98207@naver.com), 박현우(akdntmah@naver.com)

       

FAdo는 무엇일까요?

FAdo는 오토마타와 여러 계산모델에 대한 구현을 python library를 통해서 제공해줍니다. FAdo는 정규언어의 활용을 위한 대부분의 표준 연산을 제공하고 있습니다. 정규언어는 정규식 또는 유한 오토마타로 표현될 수 있는데, 이는 DFA, NFA 등으로 구현됩니다. FAdo에서는 이러한 오토마타를 파이썬 클래스로 구현합니다.

FAdo는 다음과 같은 정규표현 사이의 변환을 제공합니다.

  • NFA -> DFA : subset construction
  • NFA -> RE : recursive method

현재 수업중에 진행하고 있는 오토마타 관련 예제들을 FAdo 라이브러리를 통해 코드로 구현해보는 과정을 통해 실제로 오토마타 이론이 프로그램에 어떻게 적용될 수 있는지 경험해볼 수 있는 계기가 되길 바라겠습니다.

 

아래 순서에 따라 FAdo를 사용하기 위한 개발환경을 구축해봅시다.

Pycharm과 Conda 가상환경, Git에 대한 설치 및 구축 설명은 생략하겠습니다.

Pycharm

Conda

Git

1. Pycharm 프로젝트 생성(conda 가상환경을 선택)

2. FAdo 라이브러리 code 복사하기

python3로 구현되어있는 FAdo는 git에 올려져 있는 open source로써 클론하여 사용할 수 있습니다.

링크 복사 버튼을 눌러 클립보드에 링크를 저장합니다.

https://github.com/0xnurl/fado-python3

3. Pycharm terminal에서 git clone을 합니다.

4. FAdo를 설치합니다.

5. FAdo를 사용하기 위한 라이브러리를 설치합니다.(위 과정과 동일하게 terminal에서 진행)

pip install future

pip install graphviz

6. NFA를 만들어 DFA로 변환 후 이미지까지 확인.
nfa1 = NFA() # NFA의 객체 생성
nfa1.States = [i for i in range(11)] # NFA의 State들을 설정
nfa1.setSigma({'a', 'b', 'c'}) # transition 기호 설정
nfa1.setInitial([0]) # NFA의 Initial State 설정
nfa1.setFinal([3, 6, 10]) # NFA의 Final State 설정

nfa1.addTransition(0, 'a', 1) # NFA에 transition 추가
nfa1.addTransition(1, 'b', 2) # NFA에 transition 추가
nfa1.addTransition(2, 'c', 3) # NFA에 transition 추가

dfa1 = nfa1.toDFA() # 만든 NFA를 DFA로 변환

g = graphviz.Source(dfa1.dotFormat())
g.render() # DFA의 결과를 이미지로 확인(실행시킨 파일이 위치한 폴더에 생성됨)

7. 각종 함수에 대해서 알아보겠습니다.

Fado에서 쓰이는 여러 함수들에 대해 자세히 알고싶으시면 아래 링크를 통해 확인해주시기 바랍니다.

FAdo Function

##### 위의 함수로 NFA에서 DFA로 변환할 수 있습니다.

위의 함수로 Transition을 추가할 수 있습니다.

위의 함수로 NFA혹은 DFA가 해당하는 문자열을 인식하는지 확인 할 수 있습니다.

인식하면 True, 인식하지 못하면 False가 반환됩니다.

참고)Transition시 epsilon을 추가하고 싶을때에는 @epsilon을 사용하시면 됩니다.

Search