SLR7 Regular and context-free languages Flashcards

1
Q

﻿State transition diagram

A

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

2
Q

Finite state machines

A

“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.”

3
Q

Regular expression

A

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

4
Q

Finite sets

A

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

5
Q

Countable infinite sets

A

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

6
Q

Cardinality of a finite set

A

“The number of elements in a set.”

7
Q

Cartesian product of sets

A

“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.”

8
Q

Countable set

A

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

9
Q

Syntax diagram

A

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

10
Q

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

A

State transition diagram

11
Q

“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.”

A

Finite state machines

12
Q

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

A

Regular expression

13
Q

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

A

Finite sets

14
Q

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

A

Countable infinite sets

15
Q

“The number of elements in a set.”

A

Cardinality of a finite set

16
Q

“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.”

A

Cartesian product of sets

17
Q

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

A

Countable set

18
Q

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

A

Syntax diagram