Section 9 - Regular Languages Flashcards
what’s a Mealy machine
a finite stat machine with input
What is the cardinality of a set
the number of elements in a set
What is a Countable set
A set which can be counted off against a subset of the natural numbers, ie all the natural numbers up to a fixed limit.
A countably infinite set is one which can be counted off against the Natural numbers without ever stopping.
What is the difference between a subset and a proper subset
- subset. {0, 1 , 2 } ⊆ {0, 1, 2, 3 } where ⊆ means subset of. ⊆
includes both ⊂ and =, for example {0, 1, 2, 3 } ⊆ {0, 1, 2, 3 } is also true, because {0, 1, 2, 3 } = {0, 1, 2, 3 }. - proper subset. {0, 1 , 2 } ⊂ N where ⊂ means proper subset of, that is N contains everything in {0, 1, 2 } but there is at least one element in N that is not in {0, 1, 2 }.
What is the symbol for set difference and what does it mean?
The set difference A\B (or alternatively A-B) is defined by A\B = {x : x ∈ A and x ∉ B}.
What are the metacharacters for Regex that you should know
- (0 or more repetitions)
- (1 or more repetitions)
- ? (0 or 1 repetitions, ie optional)
- | (alternation, ie or)
- ( ) to group regular expressions. Any other metacharacters
used in an exam question will be explained as part of the question.
What’s the relationship between regular expressions and FSMs. Regular expressions and FSMs are equivalent ways of defining a regular language.
What makes a regular language “regular”
Know that a language is called regular if it can be represented by a regular expression. Also, a regular language is any language that a FSM will accept.
For a FSM what does accept and start state look like
there’s only one start state is when there’s an arrow pointing to the circle
there can be multiple accept state, they are drawn with double circles
what’s the syntax for a transition function for a Turing machine
δ(Currrent State, Input symbol) = (Next State, Outputsymbol, Movement)
eg δ(S1, 0) = (S2, 1, L)
if the machine is currently in state S1 and the input of the symbol read from the tape is 0,
then change the state to S2, write a 1 to the tape, and move left.
What’s a meta-language
a language that describes the syntax of languages. eg BNF
Syntax for Backus-Naur Form
LHS ::= RHS, where ::= means ‘is defined by’
::= is also known as a meta-symbol
,another import meta-symbol is | which means or
<point> ::=
<point> is a meta-component, or syntactic variable, they are distinguished by enclosing brackets.
</point></point>
