Automata 이론은 얼마나 실용적입니까?

1. grep / awk / sed와 같은 도구를 사용해 본 적이 있습니까? 정규 표현식은 이러한 도구의 핵심입니다.

2. 정규 표현식을 원칙적으로 사용함으로써 얼마나 많은 코딩을 피할 수 있는지 놀라게 될 것입니다. 서버.

3. 당신이 CS 전공자라면, 당신은 분명히 (적어도 작은) 언어에 대한 컴파일러 / 인터프리터를 작성하게 될 것입니다. 이 작업이 막혔을 때, 약간의 이론 (일명 문맥 자유 문법)이 얼마나 도움이 될 수 있는지 알게 될 것입니다.이 이론은 한 번 불가능했던 작업을 주말에 완료 할 수있는 것으로 만들었습니다. (그리고 그것은 발명가를 얻었습니다. 튜링 상-google BNF).

4. CS 전공자라면 어느 시점에 앉아서 컴퓨팅의 철학적 기반에 대해 생각해야합니다. 다음 버전의 Android API가 얼마나 멋진 지에 대한 것입니다. 관련 메모에서, 다음 5 년 동안 당신을 준비시키는 것이 아니라 다음 50 년 동안 당신을 준비시키는 것이 대학의 임무입니다. 그들이 할 수있는 유일한 일은 당신의 생각을 돕는 것입니다. 오토마타 이론을 그 과정 중 하나로.

더 실용적인 표현 중 하나입니다. CS의 컴파일러 구축입니다. 1965 년 Knuth는 LR 파서 연구를 시작했습니다. 신속하게 (10 년 미만), 우리는 결정 론적 푸시 다운 자동화의 하위 집합 인 LALR 파서를 사용하여 시프트 / 리 듀스 파서를 구현할 수있었습니다.

LALR 파싱의 실행 가능성과 효율성의 핵심은 다음과 같습니다. 언어의 “접두사”가 규칙적인 것으로 판명되었다는 증명 (Knuth에 의해). 이것이 yacc / bison 등과 같은 자동화 된 파서 생성기의 기원입니다.

우리가 알고있는 프로그래밍 언어가 이러한 개발에 많은 컴파일 효율성을 빚지고 있다고 말하는 것이 안전합니다.

다른 예가 있습니다. TCP / IP 프로토콜의 핵심은 유한 상태 머신입니다. 얼마나 더 실용적 일 수 있을까요?

모든 진지한 CS 학생, 특히 실용적인 학생은 오토마타 이론에주의를 기울여야합니다. 그것은 컴퓨터 과학의 많은 풍부함의 기초입니다.

주석

• 소스 파일의 구문 분석은 컴파일러에서 실제로 흥미롭고 중요한 부분이 아니므로 저는하지 않습니다. ‘ ” 프로그래밍 언어가 이러한 개발로 인해 컴파일 효율성의 대부분을 차지한다고 말하는 것이 안전하다고 생각하지 않습니다. “. 또한 PEG 또는 구문 분석 결합 자 (예 : parsec)와 같은 다른 도구를 사용하여 언어를 구문 분석 할 수 있습니다.

잡음 이 들립니까? 그것은 자동 이론의 천국에서 웃고있는 수천 개의 훌륭한 정리, 응용 프로그램 및 도구의 소리입니다.

언어와 자동 장치는 컴퓨터 과학의 모든 영역에서 찾을 수있는 우아하고 강력한 개념입니다. 언어는 건조하고 형식주의적인 컴퓨팅 선사 시대로부터 내려온 것이 아닙니다.언어 이론의 관점은 정교하고 불투명 한 대상에 대한 복잡해 보이는 질문을 단어와 나무에 대한 간단한 진술로 추출합니다. 형식 언어는 컴퓨터 과학에서 대수와 토폴로지가 고전 수학에 가져 오는 근본적이고 게임을 바꾸는 관점과 유사한 역할을합니다. 다음은 언어 이론을 통해 접근하는 실용적이고 상당히 복잡하며 실용적인 문제입니다.

1. 문서에서 중복되는 구문을 찾아 두 번째로 발생하는 것을 삭제하려고합니다. 본질적으로 언어의 시퀀스를 대체하려고합니다.
2. 프로그램에 어설 션 위반이 포함되어 있습니까? 장치 드라이버가 커널과 상호 작용할 때 특정 프로토콜을 존중합니까? 프로그램의 동작은 일련의 실행입니다. 즉, 언어입니다. 정확성 속성은 다른 언어입니다. 프로그램 정확성 문제는 언어 포함 검사에 해당합니다.
3. 소프트웨어가 무한 루프에 빠질 수 있습니까? 분산 알고리즘에 라이브 록이 포함되어 있습니까? 무한한 단어 이상의 언어가 필요하지만 언어 포함보기는 여전히 적용됩니다.
4. 웹 애플리케이션에 입력 된 악성 자바 스크립트를 탐지하기 위해 살균기를 구축하려고합니다. 악의적 인 문자열 집합은 언어입니다. 다른 언어로 양식에 입력 된 문자열 세트입니다. 이러한 언어의 교차점이 비어 있지 않은지 확인하려고합니다.
5. 반응 형 및 미션 크리티컬 시스템의 런타임 모니터링. 화학 공정의 운영을 감독하거나 재무 데이터베이스에 대한 업데이트를 추적하는 소프트웨어 모니터를 설계하려고합니다. 이는 핵심 언어 포함 및 교차 문제입니다.
6. 수많은 응용 프로그램을 통한 패턴 인식. 일련의 버그 보고서에서 텍스트의 게놈 데이터 패턴을 감지하려고합니다. 이것은 우리에게 알려지지 않은 언어의 단어가 주어지고 그 언어를 추측해야하는 문제입니다. 이것은 언어 추론 문제입니다.
7. XML 문서 세트가 주어지면 이러한 문서에 적용되는 스키마를 리버스 엔지니어링하려고합니다. XML 문서는 트리로 이상화 될 수 있습니다. 스키마는 트리 언어의 사양이고 스키마 추론 문제는 트리 언어에 대한 언어 추론 문제입니다.
8. 많은 응용 프로그램에는 자동화 된 산술 추론이 필요합니다. 자연수, 덧셈 및보다 작음 술어를 갖는 Presburger 산술과 같은 논리 이론을 수정한다고 가정합니다. n 개의 변수가있는 공식은 n 차원 벡터의 집합을 나타냅니다. 벡터는 일련의 숫자이며 단어로 인코딩 할 수 있습니다. 술어는 단어 세트입니다. 언어. 결합, 분리 및 부정과 같은 논리적 연산은 언어의 교차, 결합 및 보완이됩니다 (실존 정량화는 일종의 투영입니다).

위에서 암시 된 축소는 언어를 추상적 인 수학적 대상으로 취급합니다. 이러한 아이디어를 실제로 적용하려면 언어를 나타내는 데이터 구조와 이러한 데이터 구조를 조작하는 알고리즘이 필요합니다.

automata를 입력하십시오. Automata를 사용하면 언어와 같은 추상적 인 수학적 객체에 대한 질문을 레이블이있는 그래프에 대한 구체적이고 알고리즘적인 질문으로 줄일 수 있습니다. 엄청나게 많은 실제 응용 외에도 언어와 자동 장치 이론은 매우 중요한 지적 서비스를 제공합니다. 우편 번호 형식 지정부터 균일하고 깔끔한 개념 공간에서 모나 딕 2 차 논리에 대한 결정 절차에 이르기까지 다양한 문제에 대해 생각할 수 있습니다. 정말 놀랍습니다!

논리와 결정 절차에 대해 아무 말도하지 않았습니다. (예, 실용적인 응용 프로그램이 있습니다.) 권위있는 개요는 Kaveh의 답변을 참조하세요.

댓글

• 하하, 아이러니

다른 답변에서 설명했듯이 오토마타 이론은 우리가 잘 이해하는 간단한 계산 모델로서 개념적으로 중요합니다. 정규 표현식과 오토마타에는 실제 응용 프로그램이 많이 있습니다.

여기 “는 현대 개념을 이해하기 위해 오토마타 이론으로 돌아가는 현대 연구의 작은 예입니다. 이 백서에서 연구원들은 일반 언어에 모두 속성 테스터가 있음을 증명합니다. “정규 언어는 일정한 수의 쿼리로 테스트 할 수 있습니다.”

단순한 자동 기계가 아닙니다. 당신은 (컴퓨팅)의 기본 (상태 수용, 엡실론 전환, …)에 대해 배우고 있습니다. 무엇을 할 수 있는지, 더 중요한 것은 일부 쿼리 언어로 표현할 수없는 것을 추론하는 데 도움이되는 모델입니다. 몇 가지 흥미로운 결과는 다음과 같습니다.

• 예, 유명한 결과는 결정 론적 유한 자동 장치가 일반 언어를 인식 한다는 것입니다. 이제 알 수 있습니다. 정규식 일치를 구현하는 데 필요한 것.
• 푸시 다운 오토마타 가 문맥없는 문법 인식-이제 파서가 어떻게 생겼는지에 대한 아이디어 (또는 최소한 큰 클래스)
• 트리 자동 장치 iv id = “a284bbab04 모나 딕 2 차 논리 에 대한 문을 “>

다양한 답변에서 이미 지적했듯이 UG 과정의 Automata Theory는보다 고급 (및 실용적인) 주제를 소개하기위한 기본 개념 프레임 워크를 제공합니다. 간과 된 연결을 지적하기 위해; 예 : 이진 결정 다이어그램 (최소화 된 DFA, DFA를 가르친 후 종종 BDD 기반 퍼즐 해결을 가르칩니다.) BioPerl 및 BioPython에 포함 된 스크립팅 (실제 스크립트 정규 표현식에 의도하지 않은 일치를 얼마나 많이 숨길 수 있는지를 강화하는 훌륭한 설정), 공식 디버깅 (부정 된 FA, 교차로 속성 상태 표시), 심지어 VCR 또는 가정 침입자 경보 프로그래밍 (불완전한 예제를 통해 가르친 불완전한 자동 기계의 스트레스 상황을 매일 강조합니다. 아마도 Harel의 플레이-인 / 플레이-아웃 시나리오 기반의 사용자 인터페이스 합성을 사용하여 공식화되었습니다.) 저는 또한이 설정을 사용하여 Python의 (거의) 순수하게 가르칩니다. 지도, 람다 및 집합 이해력을 포함하는 기능적 하위 집합으로, 표준 FA 알고리즘을 코딩 할 수 있으며, 종종 수학 정의와 거의 구별 할 수없는 방식으로 작성됩니다.

댓글

• Ganesh 님, 환영합니다!
• 오토마타를 가르치는 좋은 방법입니다. 강의 노트를 공유 하시겠습니까?

오토마타 이론과 관련된 상당한 연구가있었습니다. 업계에서 사용되는 모델 검사에서. Moshe Vardi의 Fields Institute에서 최근 강의 , 특히 세 번째 강의 “Logic, Automata, Games, and Algorithms”에서 오토마타 이론이 왜 있는지 알아보십시오. 여전히 중요하고 유용합니다.

추상 :

Buechi, Elgot, Rabin 및 Buechi가 소개 한 결정 절차에 대한 자동 이론적 접근 방식 1950 년대와 1960 년대의 Trakhtenbrot는 의사 결정 절차에 대한 가장 기본적인 접근 방식 중 하나입니다. 최근 이러한 접근 방식은 하드웨어 및 소프트웨어 시스템의 공식 검증에서 산업 응용 분야를 발견했습니다. 논리에서 실용적인 알고리즘으로의 경로는 자동화뿐만 아니라 1970 년대 후반 Chandra, Kozen 및 Stockmeyer가 알고리즘 측면을 연구 한 게임을 통해.이 개요 강연에서는 자동 및 게임을 통한 논리에서 알고리즘으로의 경로를 설명합니다.

강의 슬라이드 및 오디오 파일은 다음에서 사용할 수 있습니다. 1 , 2 , 3 .

완전히 다른 실제 각도에서 또 다른 답을 내놓을 것입니다. 유한 상태 머신 (또는 최소한 몇 가지 간단한 일반화 / 확장)이 AI에서 자주 사용됩니다. 게임 프로그래밍의 측면. 그들은 캐릭터 행동을 캡슐화하기위한 훌륭한 모델을 제공하는 것으로 밝혀졌습니다. 예를 들어, 적군은 “순찰”, “수색”, “접근”, “공격”, “방어”, “후퇴”, “죽음”등을 나타내는 상태를 잘 정의 된 상태로 전환 할 수 있습니다. 이것은 정규 언어와 같은 자동 장치의 공식적인 측면을 포함하지 않지만, 자동 장치의 개념 은 매우 핵심입니다.

우리는 이론과 실제를 대조하는 언어가 하나를 다른 것보다 높게 설정하는 것이 바로 완성이라는 것을 보았습니다. 무지의 문제입니다. 그것은 사람이 생각의 첫 번째 요소에 대해 잘 모르고 있다는 것을 증명하고, 자신의 마음이 너무 변태되어 그것을 배울 수 없다는 것을 증명하는 데 큰 도움이됩니다.

— James Mill (“PQ”),“이론 및 실습”, 런던 및 웨스트 민스터 검토 , 1836 년 4 월

우리는 “실용적”과 “적용”이라는 단어의 의미를 고려해야합니다. 일부 학생의 경우 실용 은 시험에 합격하는 데 도움이되는 모든 것입니다. 다른 사람들에게는 직업에서 나올 모든 것. 두 경우 모두 Automata Theory는 매우 실용적입니다.

다른 사람들이 지적했듯이, 예를 들어 컴파일러를 공부할 때 문법을 사용합니다. 하지만 그 이상 : 서로 다른 상태와 전환 규칙이 있다는 전체 개념을 이해하면 예를 들어 코드가 여기 저기 중복되고 코드를 개선하면 더 나은 프로그래머가 될 수 있습니다. DFA 최소화 뒤에있는 동일한 개념적 아이디어 를 코드에 적용 하고 있습니다.

“응용 프로그램”과 유사합니다. 그 단어로 무엇을 이해합니까? “실질적인 엔지니어”라 할지라도 실제 프로젝트에서 Automata 이론과 유사한 아이디어를보고 사용할 수 있습니다. 프로그래밍 코드, 흐름도, 스택의 단순하지만 뛰어난 개념까지도 포함됩니다. 저와 같은 이론 전문가를 위해 저는 논리, 대수 및 유한 모델 이론과 같은 다른 영역에서 Automata 이론의 적용 을 고려합니다. 확실히, 슈퍼마켓에서 쇼핑하는 동안 펌핑 기본형을 사용할 필요는 없을 것입니다.하지만 이와 같은 정리는 구조 는 해당 언어의 논리 및 대수 구조는 말할 것도없고 특정 클래스의 언어입니다. 그리고 그것은 제가 실용성의 어떤 척도보다 더 중요하게 생각하는 것입니다.

논리와 함께 던져지는 오토마타는 automaton $ A $ 및 공식 $ \ varphi $에 대해

$ \ qquad A \ models \ varphi $

같은 상태를 확인하십시오. $ A $가 시스템의 모델이고 $ \ varphi $가 원하는 속성의 형식화이면 시스템 검증을 얻을 수 있습니다. 이는 점점 더 많은 실행 가능한 응용 프로그램에 대한 매우 실용적인 문제입니다.

사물의 자동화 측면 고려 좋은 알고리즘으로 이어집니다. 예를 들어 $ \ varphi $가 LTL 공식이고 $ A $가 Büchi 자동자 (즉, 무한하게 실행되는 유한 자동) 인 경우 $ \ varphi $를 번역 할 수 있습니다. 동등한 automaton $ A_ \ varphi $로 변경하고 $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

유한 오토마타 (종종 다른 컨텍스트에서 유한 상태 기계로 작성되거나 확률 적 변형으로 작성 됨) Hidden Markov Models는 패턴 인식 및 패턴 구조 정량화에 적용 할 수 있습니다. 예 : 주어진 확률 분포에 따라 문자열을 생성하거나 일부 분포에서 문자열 샘플 (또는 시계열)의 통계적 속성과 일치하는 문자열을 생성하는 가장 작은 확률 적 유한 오토마타는 무엇입니까?

예를 들어, 숨겨진 상태를 맹목적으로 재구성하는 알고리즘 인 CSSR 을 참조하십시오. 히든 마르코프 모델보다 더 효율적이고 유연합니다.

댓글

• 실무적인 측면에 추가하기 위해 히든 마르코프 모델은 음성 인식에 사용됩니다. Kurzweil과 같은 프로그램.

자동화 이론의 또 다른 실용적인 응용은 인공 지능의 개발입니다. 인공 지능은 유한 오토 마톤의 개념에서 개발되었습니다. 로봇의 신경망은 오토마타 이론을 기반으로 구축되었습니다. 결국 로봇도 오토마타입니다.

어떤 사람들은 그것이 산업과 어떻게 관련되는지에 관해 훌륭한 답변을주었습니다. 중요한 것은 과학적 가치이며 Automata 이론은 종종 더 높은 계층의 계산 이론을 먼저 이해하는 통로입니다. 학부생의 연구에서. Automata 이론에는 이론 컴퓨터 과학의 모든 곳에서, 특히 컴파일러와 같은 응용 프로그램에 대해 이야기하고 싶을 때 나타나는 거대한 정리 세트가 있습니다. 그것의 과학적 가치 (구식이 아닌, 어떻게 될 수 있는가? 분야의 핵심 이론)는 계산에 관심이있는 모든 과학자에게 실용적입니다. 이해하거나 원하는 사람들에게 유용한 지식이기 때문에 실용적입니다. 계산의 본질을 이해합니다. 사용을 찾을 수없는 경우, 프로그래밍 (즉, CS의 응용)이 아니기 때문에 CS를 연구하거나 연구하려는 의도에 의문을 제기합니다. >