728x90 Automata13 [Automata] Examples of Tree Structure and Regular Expression Examples of Tree Structure and Regular Expression 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Examples of Tree Structure and Regular Expression 예를 들어, 아래와 같은 Regular expression이 있다고 가정해보자. (|a(|a U b|)^*|) 해당 RE를 Tree structure로 나타내면 아래와 같다. 해당 RE를 language repres.. 2022. 5. 9. [Automata] Complexity Complexity 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Complexity Complexity는 알고리즘이 문제를 풀고 원하는 결과를 산출하는 데 걸리는 시간이 얼마나 되는지를 나타내는 걸 의미한다. Automata에서는 Polynomial time을 Turing machine으로 결과를 산출할 수 있다. 하지만 Polynomial time의 특성에 따라 방식을 나눠서 부르는데, 오토마타에서는 Class P와 Class NP,.. 2022. 5. 8. [Automata] Push Down Automata(PDA) Push Down Automata(PDA) 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Push Down Automata 이전 포스트에서 RE(Regular Expression)으로 표현이 되지 않는 경우 CFG(Context Free Grammar)로 표현한다는 것을 알아보았다. CFG로 RE 표현이 안 되는 Language를 표현하지만 이를 DFA나 NFA에 적용할 수는 없다. 따라서 CFG를 Automaton으로 나타내기 위해서는.. 2022. 5. 8. [Automata] Context Free Grammar, Palindromes Context Free Grammar, Palindromes 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Context Free Grammar 컴퓨터 프로그램을 만들기 위해서는 알고리즘이 필요하다. 사용자가 원하는 목적에 맞는 프로그램을 만들거나 특정한 프로그램을 개발하기 위해서는 알고리즘이 필요하다. 또한 알고리즘과 더불어 원하는 목적을 프로그램 방식에 맞게 구현해야 한다. 왜냐하면 사람이 당연하게 여기는 것들은 컴퓨터가 이해하지 못.. 2022. 5. 7. [Automata] Automata Prove: Infinite Countable Automata Prove: Infinite Countable 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Infinite Countable Infinite number임에도 규칙이 있으며 bijective가 된다면 countable에 해당한다. 이를 Infinite countable이라고 하며 Backward 방식을 통해 증명이 가능하다. f: N -> A such that f(n) = 2n-1 for every(all) y ∈ B .. 2022. 3. 9. [Automata] Automata Prove: Examples of Proving Sets Examples of Proving Sets 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Examples Automat에서 Set을 증명하는 방법에 대한 예제를 살펴보도록 하자. # Prove For any two sets A and B, A ∩ B ⊆ B ∩ A. 위와 같은 예제는 흔히 Set 관련 내용에서 쉽게 확인할 수 있는 문장이다. 우선은 For any two sets이기 때문에 Automata에서는 for every나 for.. 2022. 3. 9. [Automata] Automata Definitions: Yield Definition Automata Definitions: Yield Definition 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Automata Definitions Definitions을 한다고 했을 때 Tree sturcture를 활용하거나 Finite Automata를 활용해서 정의가 가능하다. 이러한 정의가 이루어지기 위해서 기본적으로 정의되어야 할 것들이 있다. Concepts being defined Concepts used Logical.. 2022. 3. 8. [Automata] Language Expression to Regular Expression Examples Language Expression to Regular Expression Examples 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Expression Algorithm을 증명하는 과정에서 표현 방법을 Language expression으로 나타낼 것인지 Regular expression으로 나타낼 건지에 차이가 있다. 이번 포스트에서는 대표적으로 많이 사용하는 LE와 RE의 차이를 예제를 통해서 살펴보도록 하겠다. Language.. 2022. 3. 8. [Automata] Deterministic Finite Automata(DFA) Deterministic Finite Automata(DFA) 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Deterministic Finite Automata(DFA) 이전 Automata 포스트에서 기본적인 정의하는 방법에 대해서 알아보았다. 이번 포스트에서는 DFA에 대해서 이야기를 해보도록 하자. Automata에는 다양한 방식의 automata 구현 방식들이 존재한다. 그렇다 보니 DFA를 정확히 이해하면 막상 어렵지 않지만 .. 2022. 3. 8. [Automata] Prove Statements Prove Statements 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Prove Statement Statement에 대한 정의까지 알아봤으니, Statement를 증명하는 것에 대해서 알아보도록 하자. Statement를 보다 쉽게 증명하기 위해서는 2가지 방법을 사용해볼 수 있다. 우선적으로는 Tree structure를 사용하여 시각적으로 특정 Statement가 어떤 구조인지를 파악한다. 이후에 Tree structure를.. 2022. 3. 8. [Automata] Statement Statement 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Statement Automata에서 Statement은 아래와 같은 구성 요소를 포함하고 있다. Concepts Logical symbols Statement를 정의하기 위해서는 Concepts과 Logical symbols들을 통해 가능하다. Concept은 Concept name, parameter, input, output으로 정의되며, Logical symbol은 .. 2022. 3. 7. [Automata] Function and Concept Function and Concept 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Functions Functions이라고 하면 Programming을 공부했던 사람이라면 누구나 알고 있는 용어이다. Function을 생각하면 다양한 것들이 있겠지만 sum과 같은 standard function이 생각난다. 하지만 특정 Function이 무엇이고 어떤 것들이 있으며, 어떻게 사용하는지는 알지만 Function에 대한 정확한 정의는 모르.. 2022. 3. 7. [Automata] Automata란? Automata란? 포스트 난이도: HOO_Junior [Notice] 포스트 난이도에 대한 설명 안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다 whoishoo.tistory.com # Automata Theory 오토마타 이론(Automata theory)은 현재 Computing에 있어서 Algorithms들에 대한 이론적인 부분이라고 알려져 있다. 사실 오토마타는 컴퓨터가 발전하고 나온 컴퓨터 알고리즘 이론이라기보다는 기존부터 있던 알고리즘 이론이다. 알고리즘이라는 것 자체가 기원전 2500년때 부터 이미 사용되어오고 있다는 점에서 오토마타 이론은 .. 2022. 3. 7. 이전 1 다음 728x90
