Regular And Context Free Languages Flashcards
(17 cards)
What is a FSM
A machine that has a fixed number of states and a set of possible inputs. These change the state.
Why are FSM always deterministic
There is definitely path for 1 input
What is non deterministic FSM
There are multiple paths for a single input.
What is a set
Unsorted collection of different objects.each value occurs only once.
What is the cardinals of a set
The number of elements in the set
What is a countable set
A set that counted of by the natural numbers.
What is a finite set
There is only n elements in the set where n is a positive integer
What is countable infinite
Placed in to a one to one correspondence to a natural number
Uncountable set is
When you can’t list all the items in the set
What is a subset
Has to have all elements of the set and a few more.
What is a proper subset
What is a regular expression
Specifies the valid strings in a language in rules.
What is a regular language
A language that a FSM will accept.
What is BNF
A visual representation of a regular language
How does BNF work
