# SLR7 Regular and context-free languages Flashcards

State transition diagram

“A diagram consisting of circles to represent states and directed line segments to represent transitions between the states.”

Finite state machines

“A mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time.”

Regular expression

“A sequence of symbols and characters expressing a string or pattern to be searched for within a longer piece of text.”

Finite sets

“A set whose elements can be counted off by natural numbers up to a particular number.”

Countable infinite sets

“A set that can be counted off by the natural numbers.”

Cardinality of a finite set

“The number of elements in a set.”

Cartesian product of sets

“Two sets, X and Y, written X x Y and read ‘X cross Y’, is the set of all ordered pairs (a, b) where a is a member of A and b is a member of B.”

Countable set

“A countable set is a set with the same cardinality (number of elements) as some subset of natural numbers.”

Syntax diagram

“A way to represent context-free grammar. They represent a graphical alternative to Backus–Naur form (BNF) as metalanguages.”

“A diagram consisting of circles to represent states and directed line segments to represent transitions between the states.”

State transition diagram

“A mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time.”

Finite state machines

“A sequence of symbols and characters expressing a string or pattern to be searched for within a longer piece of text.”

Regular expression

“A set whose elements can be counted off by natural numbers up to a particular number.”

Finite sets

“A set that can be counted off by the natural numbers.”

Countable infinite sets

“The number of elements in a set.”

Cardinality of a finite set