Questions and Answers
What is a set with only one element called?
An empty set is also referred to as a void set.
True
The number of subsets in a set with n elements is given by the formula ___.
2^n
Match the set type with its description:
Signup and view all the answers
What is the purpose of a state in automata theory?
Signup and view all the answers
Which type of machine is considered a 'counting machine'?
Signup and view all the answers
What does GNF (Greibach Normal Form) grammar consist of?
Signup and view all the answers
What does a Pushdown Automata (PDA) implement?
Signup and view all the answers
A Pushdown Automata can remember a finite amount of information.
Signup and view all the answers
An Instantaneous Description is represented by a triplet of (q, w, s) which stands for state __, unconsumed input __, and stack contents __.
Signup and view all the answers
Match the following fundamental operations of a Turing Machine:
Signup and view all the answers
Study Notes
Elements and Sets
- An element is a well-defined object.
- A set is a collection of well-defined objects, represented by a capital letter.
Method of Set Notation
- Roster/Tabular/List Method: represents a set by listing its elements, separated by commas and enclosed in curly brackets.
- Set Builder/Rule Method: defines a set by stating a property that characterizes all its elements.
Types of Sets
- Finite Set: a set with countable elements.
- Infinite Set: a set with uncountable elements.
- Empty Set (Null or Void Set): a set with no elements, denoted by {}.
- Unit Set (Singleton): a set with only one element.
- Subset: every element of set A is also an element of set B, denoted by A ⊆ B.
- Proper Subset: at least one element in B is not contained in A, denoted by A ⊂ B.
- Family Set: a class of sets or the set of sets.
- Power Set: the set of all subsets of a given set, denoted by P(A).
- Universal Set: a set that contains all objects, including itself.
Cardinality
- The number of elements in a set.
Set Relations
- Equal Sets: same elements and same cardinality.
- Equivalent Sets: same cardinality.
- Disjoint Sets: no common elements, different cardinalities.
Set Operations
- Union: contains all elements of the sets involved.
- Intersection: contains exactly the common elements of the sets involved.
- Set Difference: contains everything in the minuend but not in the subtrahend.
Relations
- A relationship between elements of two sets.
- Types of Relations:
- Reflexive Relation: every element is related to itself.
- Symmetric Relation: any element pair is related to each other.
- Transitive Relation: if one element is related to a second, and the second is related to a third, then the first element is also related to the third.
- Equivalent Relation: a relation that is reflexive, symmetric, and transitive.
Functions
- A way of matching members from set "A" to set "B".
- Injective Function: one-to-one relationship.
- Surjective Function: each element of B has a pair.
- Bijective Function: both injective and surjective.
- Inclusion Function: domain is a subset of its codomain.
Graph Theory
- A bunch of vertices (Nodes) represented by circles, connected by edges represented by lines.
- Tree: an undirected graph, any two vertices are connected by exactly one simple path, and does not contain a cycle.
- Adjacent Vertices: a pair of vertices that determine an edge are "adjacent" vertices.
- Circuit: a path that begins and ends at the same vertex.
- Simple Path: no vertex appears more than once in the vertex sequence.
- Connected Graph: there is a path from any vertex to any other vertex in the graph.
- Disconnected Graph: there is no path from any vertex to any other vertex in the graph.
- Component: occurs only to disconnected graphs, connected pieces of the graph.
- Simple Cycle: one that does not repeat any node except for the first and last.
Automata Theory (Theory of Computation)
- A theoretical branch of computer science, established during the 20th century.
- Pure mathematics of computer science, theory of what can and cannot be computed.
History of Automata
- 1936: First Infinite Model by Alan Turing
- 1943: First description of finite automata by Warren McCulloch and Walter Pitts
- 1955: Generalized Automata Theory for Machines by G.H.Mealy and E.F.Moore
Alphabet and String
- Alphabet: a finite, nonempty set of symbols, denoted by Σ.
- String: a list of symbols from an alphabet.
Language
- A set of strings from the same alphabet.
Finite Automate
- A state diagram that comprehensively captures all the possible states and transitions that a machine can take as a response to inputs.
- Recognizer for "Regular Languages".
Deterministic Finite Automaton (DFA)
- An automaton that cannot be in more than one state at any one time.
- Does not accept empty strings.
Nondeterministic Finite Automaton (NFA)
- An automaton that may be in several states at once.
- Allows zero, or more for every input symbol.
State Diagram (Transition Graph)
- A directed graph where vertices represent the internal state of the automaton, and the edges represent the transitions.
Dead State
- A non-final state that transits itself for all input symbols.
Regular Expression
- A simple expression that describes the languages accepted by a FA.
- Sequence of characters that forms a search pattern, mainly for use in pattern matching with strings or string matching.
Regular Set
- A set accepted by a finite automaton.
Closure
- A set is closed under an operation if, whenever the operation is applied to members of the set, the result is also a member of the set.
Operators of Regular Expression
- Union: set of strings that are in either L1 or L2, or both.
- Concatenation: set of strings formed by taking any string and concatenating it with any string.
- Kleene Closure(*): set of strings that can be formed by taking any number of strings, including the null string.
- Positive Closure(+): set of strings that can be formed by taking any number of strings, excluding the null string.
Moore Machines
- Its output depends only on the present state.
- Considered as "counting machine".
- Has 6 tuples: Q, q0, Σ, O, δ, and λ.
Mealy Machine
- Its output depends only on the present state and current input symbol.
- Considered as "output producer".
Context-Free Grammar (CFG)
- Also known as Backus-Naur Form (BNF).
- Has 4 tuples: V, T, S, and P.
Derivation [of strings]
- Generation of language using specific rules.
Regular Grammar
- Right Linear Grammar: non-terminal symbol appears at the end of the production.
- Left Linear Grammar: non-terminal symbol appears at the beginning of the production.
Derivation Tree
- Also known as Parse Tree.
- An ordered rooted tree that graphically represents the semantic information of strings derived from CFG.
Approach to Draw a Derivation Tree
- Top-down Approach: starts with the starting symbol, then goes down to tree leaves using productions.
- Bottom-up Approach: starts from tree leaves, then proceeds upward to the root (starting symbol).
Sentential Form
- Partial derivation tree contains the root.
Types of Derivation Tree
- Left Derivation Tree: obtained by applying production to the leftmost variable in each step.
- Right Derivation Tree: obtained by applying production to the rightmost variable in each step.
Ambiguous Grammar
- Grammar where exists two or more derivation trees for some strings.
Simplification
- Reduction of CFG.
- Elimination of production rules and symbols that are not needed for derivation of strings.
Chomsky Normal Form (CNF)
- A context-free grammar where every production rule is of the form: A -> BC or A -> a.
Greibach Normal Form (GNF)
- For every CFL without epsilon, there exists a grammar in which every production is of the form: A → aV where A is a variable, a is exactly one terminal, V is the string of none or more variables.
Pushdown Automata (PDA)
- A way to implement a context-free grammar in a similar way that a DFA is designed for a regular grammar.
- Can remember infinite amount of information.
- Equal to NFA with a stack.
Instantaneous Description
- Represented by a triplet (tuples): q, w, and s.
Turnstile Notation
- Used for connecting pairs of ID’s that represent one or many moves of a PDA.
- Denoted by "⊢".
Parsing
- Used to derive a string using the production rules of a grammar.
- Top-Down Parser: starts from the top with the start-symbol.
- Bottom-Up Parser: starts from the bottom and comes to the start symbol.
Turing Machine
- Proposed by Alan M. Turing (1912-1954).
- A hypothetical machine in 1936 whose computations are intended to give an operational and formal definition of the intuitive notion of computability in the discrete domains.
- Mathematical model which consists of an infinite length tape divided into cells on which input is given.
6 Types of Fundamental Operations
- Read
- Write
- Move tape left
- Move tape right
- Change state
- Halt
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
This quiz covers the basics of sets, including elements, set notation methods, and types of sets. Learn about finite and infinite sets, roster method, and set builder method.
