Fichas
Unit 9
Fichas del conjunto (31)
- 1Mealy Machine- Is a type of FSM, generating an output determined by the input and current state
- Has the notation input/output as the transition condition - 2Uses of Mealy Machines- In language parsing
- To translate languages - 3State transition tables ...- May be used to define Mealy Machines
- Shows all possible states and inputs - 4How are sets represented?A = {0, 1, 2, 3}
- 5Common sets- N, Natural numbers, {0, 1, 2, 3}
- Z, All integers, {-2, -1, 0, 1, 2}
- Z^+, Positive integers, {1, 2, 3}
- Q, Rational numbers, anything that can be represented as a fraction
- R, real numbers, anything that can be represented on a number line - 6Set membership- X ∈ S, X is a member of set S
- X ∉ S, X is not a member of set S - 7Symbols in sets:| : such that
^ : is a member of
A \ B : Members of A that aren't in B
A U B : Members of A or B
A ∩ B : Members of A and B - 8Subsets- A ⊆ B : A is a subset of B, when every member of A is also a member of B
- A ⊈ B : A is not a subset of B, if at least one member of A is not a member of B
- A ⊂ B : A is a proper subset of B, when A is a subset of B but A ≠ B - 9Cartesian product notation- A = (1,2), B = (4,8)
- A x B = {(1,4), (1,8), (2,4), (2,8)} - 10Cardinality- The number of items within a set
- This is denoted by |A| - 11Infinite and countably infinite- An infinite set contains an infinite number of distinct members
- A countably infinite set is one whose members can be counted using the set N - 12Set comprehension and compact representation- S = { x | x ∈ N ^ x is even }
- S = { x ∈ N | x is even } - 13What is a regular expression?A regular expression is a pattern used to specify a set of strings
- 14Regular expressions are used for:- Finding particular words in a string
- Finding combinations of characters in strings
- Defining a set of acceptable strings in a language - 15Symbols in regular expressions:| : or
* : 0 or more of an item
+ : 1 or more or an item
? : 0 or 1 of an item
() : used to group items - 16FSM's in regular expression- Finite state machines are used to check if expressions are valid
- They must include a reject state - 17The Turing machine- Is a computer with a single fixed program
- Has a finite set of states
- Has a finite alphabet of symbols
- Has an infinite tape filled with squares
- Has a sensing read/write head
- Must have a start state and at least one end state - 18What is a controller?A controller is a Finite State Machine telling the Turing machine what to do
- 19The transition functionδ (Current state, Input symbol) = (Next state, output symbol, Head move)
- 20Why are Turing machines important?- Turing machines provide a definition of what's computable
- Can be defined to represent any computation
- However a different Turing machine is needed for individual operations - 21Universal Turing MachineIs capable of computing anything that is computable
- 22What is Backus-Naur form?Backus-Naur form is a formal written notation used to describe the syntax rules of a language
- 23What is a meta language?- A language that describes another language
- Backus-Naur is a meta language - 24Symbols for Backus-Naur form::= : Is defined as
| : or
<> : surrounds category names
e.g. :
::= 0|1|2|3|4|5|6|7|8|9 - 25Recursion in Backus-Naur formProduction rules can call themselves to initiate recursion
e.g.:
::= | - 26What are syntax diagrams?Syntax diagrams are another way of representing context free languages
- 27Why use Reverse Polish Notation?- It eliminates the need for brackets in
sub-expressions
- The algorithm for evaluating postfix expressions is simpler than infix expressions - 28Order of precedence in Reverse Polish Notation~
^
*, /
+, -
= - 29Methods of converting infix to RPN (postfix)- Numbering
- Bracketing
- Binary tree - 30Methods of converting RPN to infix- Scanning
- Bracketing - 31Why are stacks used in RPN?Stacks are used to evaluate RPN expressions to produce a result for the equation
Información
- Descripción
- Fichas sobre Unit 9, creado por . . el 28/05/2019.
- Creado por
- . .
- Visitas
- 2
- Valoración