Regular Languages

• What is a finite state machine?

  A computational model with states and transitions

  
• What happens when a 1 is inputted at S0?

  The state changes to S1

  
• What is a set in programming?

  An abstract data type with unique values
• Can sets contain other sets?

  Yes, sets can contain other sets
• What is the notation for a set of farm animals?

  1. {"Pig", "Goat", "Cow", "Sheep"}
• What does set comprehension allow you to do?

  Create a set from a general set
• What is the first condition in the set comprehension S={x*3|x∈ℤ ∧ x≥-3 ∧ x<3}?

  Only integers greater than or equal to -3
• What is the second condition in the set comprehension S={x*3|x∈ℤ ∧ x≥-3 ∧ x<3}?

  Only integers below 3
• How do we create a set of the first 10 square numbers?

  S={x*x|x∈ℕ ∧ 9≥x}
• What is compact set representation?

  A space-efficient way of describing sets
• What does the set {0^n 1^n | n ≥ 1} represent?

  Strings with equal number of 0s and 1s

  
• What are finite sets?


  Sets with a finite number of items
• What is the cardinality of a finite set?

  The number of elements in a set
• What are infinite sets?

  Sets with an infinite number of items
• What are countably infinite sets?

  Sets that can be counted by natural numbers
• What is an example of a countably infinite set?

  The set of numbers divisible by three
• What misconception can occur with countably infinite sets?

  Thinking they are larger than natural numbers
• What is the cardinality of the set {(1,2),(2,4),(3,6),(4,8),(5,10),(6,12),(7,14),(8,16),(9,18),(10,20)}?

  10
• How do infinite sets differ from finite sets?

  Infinite sets contain an infinite number of items
• What are the two types of infinite sets?

  Countable and non-countable sets
• What defines a countably infinite set?

  Items can be counted by natural numbers
• Give an example of a countably infinite set.

  The set of integers
• What is a non-countable set?

  A set that cannot be paired with natural numbers
• What is a proper subset?

  A subset that is not equal to the original set
• What defines countable sets?

  Same cardinality as a subset of natural numbers
• What does the symbol ∈ denote?

  An item is in a set
• How do regular expressions relate to finite state machines (FSMs)?

  • Each regular expression has an equivalent FSM
  • FSMs recognize patterns described by regular expressions
• What does the notation a+(bc)* describe?

  One or more a's followed by zero or more bc's

  
• What does the notation abc* signify in an FSM?

  abc must appear at least once
• What does the * and ? signify in an FSM?

  They are optional and can repeat