1. these real computers are quite complicated-too much so to allow us to set up a manageable mathematical theory of them directly. Instead we use an idealized computer called a computational model.
2. This controller is a computer that has just a single bit of memory, capable of recording which of the two states the controller is in. Other common devices have controllers with somewhat larger memories. In an elevator controller a state may represent the floor the elevator is on and the inputs might be the signals received from the buttons.
3. A Markov chain (discrete-time Markov chain or DTMC[1]), named after Andrey Markov, is a random process that undergoes transitions from one state to another on a state space.4. each diagram usually represents objects of a single class and track the different states of its objects through the system
5. In automata theory and sequential logic, a state transition table is a table showing what state (or states in the case of a nondeterministic finite automaton) a finite semiautomaton or finite state machine will move to, based on the current state and other inputs.
6. In automata theory, a finite state machine is called a deterministic finite automaton (DFA), if 1) each of its transitions is uniquely determined by its source state and input symbol, and 2) reading an input symbol is required for each state transition.
7. A nondeterministic finite automaton (NFA), or nondeterministic finite state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA.
8. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings.
9. Unlike a DFA, it is non-deterministic, i.e., for some state and input symbol, the next state may be one of two or more possible states.
10. In theoretical computer science and formal language theory, a regular expression (sometimes called a rational expression)[1][2] is a sequence of characters that define a search pattern, mainly for use in pattern matching with strings, or string matching, i.e. "find and replace"-like operations.
11. In theoretical computer science and formal language theory, a regular language (also called a rational language[1][2]) is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science (as opposed to many regular expressions engines provided by modern programming languages, which are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression).
12. Regular languages are very useful in input parsing and programming language design.
14. Nondeterministic finite automata are useful in several respects. As we will show, every NFA can be converted into an equivalent DFA, and constructing NFAs is sometimes easier than directly constructing DFAs
15. every NFA can be converted into an equivalent DFA, but sometimes that DFA may have many more states. The smallest DFA for A contains eight states. Furthermore, understanding the functioning of the NFA is much easier, as you may see by examining the following figure for the DFA.
16. In the automata theory, a nondeterministic finite automaton with ε-moves (NFA-ε)(also known as NFA-λ) is an extension of nondeterministic finite automaton(NFA), which allows a transformation to a new state without consuming any input symbols.
17. The transitions without consuming an input symbol are called ε-transitions or λ-transitions. In the state diagrams, they are usually labeled with the Greek letter ε or λ.
18. NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA. Since a NFA-ε can always be transformed into a NFA, the properties are also true for NFAs.
19. In a DFA the transition function takes a state and an input symbol and produces the next state. In an NFA the transition function takes a state and an input symbol or the empty string and produces the set of possible next states.
20. a regular language has a DFA recognizing it and any DFA is also an NFA.
21. The value of the arithmetic expression is the number 32. The value of a regular expression is a language.
22. In regular expressions, the star operation is done first, followed by concatenation, and finally union, unless parentheses are used to change the usual order.
23. The expression E represents the language containing a single string-namely, the empty string-whereas 0 represents the language that doesn't contain any strings
24. any regular expression can be converted into a finite automaton that recognizes the language it describes, and vice versa. Recall that a regular language is one that is recognized by some finite automaton.
25. A language is regular if and only if some regular expression describes it.
26. Automata theory deals with the definitions and properties of mathematical models of computation. These models play a role in several applied areas of computer science. One model, called the finite automaton, is used in text processing, compilers, and hardware design. Another model, called the context-free grammar, is used in programming languages and artificial intelligence
27. If A is the set of all strings that machine M accepts, we say that A is the language of machine M and write L(M) = A.We say that M recognizes A or that M accepts A. Because the term accept has different meanings when we refer to machines accepting strings and machines accepting languages, we prefer the term recognize for languages in order to avoid confusion.
28. A machine may accept several strings, but it always recognizes only one language. If the machine accepts no strings, it still recognizes one languagenamely, the empty language 0.
29. In the theory of computation the objects are languages and the tools include operations specifically designed for manipulating them. We define three operations on languages, called the regular operations, and use them to study properties of the regular languages
30. 计算机控制系统的控制程序具有有限状态自动机（FA）的特征，可以用有限状态机理论来描述。有限自动机（Finite Automata Machine）是计算机科学的重要基石，它在软件开发领域内通常被称作有限状态机（Finite State Machine），是一种应用非常广泛的软件设计模式。
31. Generalized nondeterministic finite automata are simply nondeterministic finite automata wherein the transition arrows may have any regular expressions as labels, instead of only members of the alphabet or E.
32. The property states that all strings in the language can be "pumped" if they are at least as long as a certain special value, called the pumping length. That means each such string contains a section that can be repeated any number of times with the resulting string remaining in the language.
33. context-free grammars, a more powerful method of describing languages. Such grammars can describe certain features that have a recursive structure, which makes them useful in a variety of applications.
36. pushdown automata, a class of machines recognizing the context-free languages. Pushdown automata are useful because they allow us to gain additional insight into the power of context-free grammars.
37. All strings generated in this way constitute the language of the grammar. We write L(G 1) for the language of grammar G1 . Some experimentation with the grammar G1 shows us that L(G1 ) is {On#n1 j n > O}. Any language that can be generated by some context-free grammar is called a context-free language (CFL).
38. A compiler translates code written in a programming language into another form, usually one more suitable for execution. To do so the compiler extracts the meaning of the code to be compiled in a process called parsing
39. As with the design of finite automata, discussed in Section 1.1 (page 41), the design of context-free grammars requires creativity. Indeed, context-free grammars are even trickier to construct than finite automata because we are more accustomed to programming a machine for specific tasks than we are to describing languages with grammars
40, Solving several simpler problems is often easier than solving one complicated problem.
41. If a grammar generates the same string in several different ways, we say that the string is derived ambiguously in that grammar. If a grammar generates some string ambiguously we say that the grammar is ambiguous.
42. Natural language processing (NLP) is a field of computer science, artificial intelligence, and computational linguistics concerned with the interactions between computers and human (natural) languages. As such, NLP is related to the area of human–computer interaction. Many challenges in NLP involve natural language understanding, that is, enabling computers to derive meaning from human or natural language input, and others involve natural language generation.
43. When we say that a grammar generates a string ambiguously, we mean that the string has two different parse trees, not two different derivations.
44. Pushdown Automata are like nondeterministic finite automata but have an extra component called a stack. The stack allows pushdown automata to recognize some nonregular languages.
45. Pushdown automata are equivalent in power to context-free grammars. This equivalence is useful because it gives us two options for proving that a language is context free. We can give either a context-free grammar generating it or a pushdown automaton recognizing it. Certain languages are more easily described in terms of generators, whereas others are more easily described in terms of recognizers.
46. Recognizer vs Generator
47. A programmable logic device (PLD) is an electronic component used to build reconfigurable digital circuits.
48. In digital circuit theory, combinational logic (sometimes also referred to as time-independent logic[1] ) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only
49. Digital electronics or digital (electronic) circuits are electronics that handle digital signals - discrete bands of analog levels - rather than by continuous ranges (as used in analogue electronics).
50. In most cases, the number of these states is two, and they are represented by two voltage bands: one near a reference value (typically termed as "ground" or zero volts), and the other a value near the supply voltage. These correspond to the "false" ("0") and "true" ("1") values of the Boolean domain respectively, named after its inventor, George Boole, yielding binary code.
60. In electronics, a logic gate is an idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more logical inputs, and produces a single logical output.
61. sequential logic has memory while combinational logic does not.
62. In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively.
63. Combinational logic is used in computer circuits to perform Boolean algebra on input signals and on stored data.
64. Practical circuits will have a mix of combinational and sequential logic, with sequential logic making sure everything happens in order and combinational logic performing functions like arithmetic, logic, or conversion.
65. Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages. Mainly the former are used in parser design.
66. the unlimited nature of a stack allows the PDA to store numbers of unbounded size.
67. The domain of the transition function is Q x SE x rF. Thus the current state, next input symbol read, and top symbol of the stack determine the next move of a pushdown automaton.
68. A language is context free if and only if some pushdown automaton recognizes it.
69. The point is, a computer scientist is not satisfied until they actually run an experiment on a computer. In fact, they aren’t satisfied until they run a lot of experiments on a computer. Whereas for a mathematician, the proof is enough. The proof in fact, is the proof that something is true or not. Whereas the computer scientist requires physical results. This seems to me a curious fact.
70. I think this is why computer scientists refer to themselves as scientists, because CS is an experimental science. Mathematics is too, in the sense that both disciplines play with thought experiments. Mathematicians simply choose to do their thought experiments on paper, where as computer scientists prefer screens.
NFAs have been generalized in multiple ways, e.g.,
nondeterministic finite automaton with ε-moves,
finite state transducers,
pushdown automata,
ω-automata,
and probabilistic automata.
Terms:
Finite State Machine
Finite Automation
State Diagram
State Transition Table
Deterministic Finite Automation
Non-Deterministic Finite Automation
NFA [Used for Regular Expression]
DFA
GNFA
NFA-εs
Formal Definition [With mathematics]
Regular
Regular Expression
Regular Language
Theorem
Corollary
Lemma
Pumping Lemma
pigeonhole principle
Grammar,
Parser
Pushdown Automata
Derivation
PDA
Context-Free Grammar:
Substitute Rules
Productions
Variable
Terminals
CFG
Parse Tree
Grammar
Syntax
Semantics
Context-Free Language
Chomsky Normal Form
Conversion
PDA:
Lemma
Circuits
Languages:
Context-Free Languages
Regular Languages
Conversion Tasks:
1. Convert NFA -> DFA
2. Convert DFA -> NFA -> GNFA
3. Convert GNFA -> Regular Expression
4. Convert Language -> CFG
5. DFA -> CFG
Computational Model:
DFA
NFA
GNFA
Regular Language
Non Regular Language
CFG
Pushdown Automata
You use a grammar to describe a language by generating each string of that language in the following manner:
1. Write down the start variable. It is the variable on the left-hand side of the top rule, unless specified otherwise.
2. Find a variable that is written down and a rule that starts with that variable. Replace the written down variable with the right-hand side of that rule.
3. Repeat step 2 until no variables remain
Questions:
1. Computer Science vs Mathematics
References:
https://en.wikipedia.org/wiki/Markov_chain
https://en.wikipedia.org/wiki/State_transition_table
https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton#Example
https://en.wikipedia.org/wiki/Regular_expression
https://en.wikipedia.org/wiki/Greek_alphabet
https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton_with_%CE%B5-moves
http://baike.baidu.com/view/409351.htm
https://en.wikipedia.org/wiki/Parsing
https://en.wikipedia.org/wiki/Digital_electronics
https://en.wikipedia.org/wiki/Logic_gate
https://en.wikipedia.org/wiki/Boolean_algebra
http://faculty.etsu.edu/tarnoff/ntes2150/balgebra/balgebra.htm
http://www.scott-a-s.com/cs-is-not-math/
https://www.quora.com/Why-should-I-choose-computer-science-over-mathematics
http://cs.nyu.edu/acm/wordpress/?p=145
No comments:
Post a Comment