美文网首页
计算理论笔记

计算理论笔记

作者: zongmumask | 来源:发表于2021-02-13 11:55 被阅读0次

Concepts

  • formal language: set of strings
  • string: a sequence of symbols from an alphabet
  • alphabet: a finite set of symbols
  • finite automata: can be used to recognize certain languages
  • deterministic finite automata: DFAs, have exactly one transition out of each state for each symbol in the alphabet
  • two DFAs equivalent if they recognize the same laguage
  • image
  • in a NFA a string is accepted if there exits at least one path from the start state to accept state
  • image
  • image
  • DFA and NFA's graph deepth is the number of symbols in the processing string
  • regular language is a language that can recognize by a DFA or NFA or a regular expression

NFA to DFA conversion

  • NFA to DFA conversion: thinking of a combination of the states in the NFA as a single state in DFA that you are constructing
  • the subset construction: the state in DFA we are constructing is a subset of states in NFA
  • the number of subsets is 2 power N(the number of states count)
  • epsilon closure(q0): the epsilon closure of q0 is q0 itself plus all the states that can be reached from q0 via epsilon transitions
  • image
  • image
  • the start state in the target DFA is the epsilon-closure of the start state in the original NFA
  • a state(set of NFA states) in the DFA ia an accept state if at least one of the states that constitute the state corresponds to an accept state in the original NFA
  • conversion make trap state explicit

Regular operations and Regular expression

  • concatenation: every state belongs to that language has to have two pieces, a prefix and suffix.the prefix belongs to language one, the suffix belongs to language two.
  • regular operations: union, concatenation, star
  • image
  • 321613288571_.pic_hd.jpg
  • 331613288814_.pic_hd.jpg
  • precedence: star (exponential) concatenation (mult) union (add)
  • Union


    361613742550_.pic_hd.jpg
    371613742678_.pic_hd.jpg
  • Concatenation


    391613744027_.pic_hd.jpg
    381613744011_.pic_hd.jpg
  • Star


    401613745083_.pic_hd.jpg
    411613745629_.pic_hd.jpg
  • convert regular expression to NFA


    431613747777_.pic_hd.jpg
  • compiler: regular expression(define the language sytax) -> NFA (subset construction) -> DFA
  • 451613908220_.pic_hd.jpg
  • 461613908661_.pic_hd.jpg
  • 471613909295_.pic_hd.jpg

Grammars

  • a context-free grammar is quadruple (V, T, P, S)


    481614005194_.pic_hd.jpg
  • a linear grammar is a grammar in which there is at most one variable on the right-hand side of any production (grammar rule)


    501614090371_.pic_hd.jpg
  • a regular grammar is a grammar that all productions are left-linear or right-linear
  • a language is regular if there exits at least one regular grammar that generates it

相关文章

  • 计算理论笔记

    Concepts formal language: set of strings string: a sequen...

  • 可计算问题笔记

    可计算问题理论笔记 计算机可以求解哪些问题? 求解计算问题的思路 衡量求解计算问题的算法优劣--复杂度分析 复杂度...

  • 计算理论导引 阅读笔记-1

    图灵机与可计算性理论 在介绍图灵机前先来简略了解一下哥德尔完备性: 哥德尔完备性定理成立。它声称对于任何一阶理论T...

  • 计算理论导引 阅读笔记-2

    图灵机的形式化 一台图灵机是一个七元组[2],{Q,Σ,Γ,δ,q0,qaccept,qreject},其中 Q,...

  • 计算机组成原理与体系结构笔记(3.3)C语言中的整数

    计算机组成原理与体系结构笔记(3.2)带符号整数的表示 理论和实践缺一不可......如果懒得看理论,也请实践一下...

  • Atitit软件理论方面的书籍

    Atitit软件理论方面的书籍 目录 1. 计算机科学分为计算机理论和计算机应用。计算机基础理论包含以下几部分: ...

  • PAC 可学习性

    计算理论研究什么时候一个问题是可被计算的,而 PAC 学习理论,或者说计算学习理论 (Computational ...

  • 【西瓜书】 第12章 计算学习理论

    计算学习理论(computational learning theory)是通过“计算”来研究机器学习的理论,简而...

  • 心智计算理论:智能即计算

    01 关于心智有两个深刻的问题:“智能怎么产生”、“意识怎么产生”。 如果说随着认知神经科学的发展,智能能够部分地...

  • 并发编程之基础篇

    一、计算机理论模型与工作原理 1、理论模型 --> 现代计算机都是基于:冯诺依曼计算机模型运行过程:内存中获取...

网友评论

      本文标题:计算理论笔记

      本文链接:https://www.haomeiwen.com/subject/zpysxltx.html