• 학생 - 선생
• 학생은 선생님에게 두가지 종류의 질문을 질문할 수 있음
  1. Membership Query : word w 가 언어 L 에 속하는지 아닌지 선생님은 yes or no를 답함
  2. Equivalence Query : DFA H가 L을 허용하는지 아닌지 여부. 허용하면 True 아니면 반례를 리턴함 x ∈ L\\L(H) ∪ L(H)\\L → L(H)는 무슨 뜻?
• 언어 L을 성공적으로 학습하려면 유한한 쿼리 내에서 DFA를 잘 guess 해야함.
• Language 라 하는 것은

예제: 로그인 프로토콜 추론

L* 알고리즘을 사용하여 네트워크 프로토콜을 추론하는 예제를 살펴보자.

아래는 학습자가 **네트워크 프로토콜의 상태와 동작(==Language)**을 추론하기 위해 L 알고리즘을 적용하는 방식을 나타낸다.

예를 들어, 간단한 로그인 프로토콜을 추론한다고 가정한다.

프로토콜 동작 가정

가상의 로그인 프로토콜이 다음과 같이 작동한다고 가정:

1. 사용자가 "LOGIN" 명령어를 보내면 서버는 "OK" 응답을 보냄
2. 사용자가 "AUTH" 명령어와 올바른 비밀번호를 함께 보내면, 서버는 "WELCOME" 응답을 보냄
3. 올바르지 않은 명령어를 보내면, 서버는 "ERROR"를 반환

이후 L* 알고리즘을 이용하여 이 로그인 프로토콜의 상태 머신을 추론

우리가 원하는 것 : 로그인 프로토콜의 상태머신 (DFA)를 추론

우리가 할 수 있는 것 : 선생님(서버)에게 질문(쿼리)를 날리고 그 결과 값을 받아올 수 있음.

1. 초기 설정

• 학습자: 프로토콜의 상태와 전이 규칙(==language)을 모르는 상태에서, 서버(선생님)에게 쿼리 보냄