Chapter 1: Regular Languages (FA, Nondeterminism, Reg Expressions, Nonreg Languages)

Question 1

What is a finite automaton (FA)?

Answer 1

Also known as a Finite State Machine (FSM)

• A simple model of computation, for machines with very limited memory (automatic door, elevator, digital watch)
• Good for emulating simple/few instructions
• Useful when attempting to recognize patterns

Informally, consists of:

• States
• Transitions
• 1 start state
• 1+ final states
• Alphabet

Question 2

What is computability theory?

Answer 2

• Deals with the mathematical basis for Computer Science
• Help us answer the question: “What can and cannot be computed”

Question 3

What is a computational model?

Answer 3

Mathematical object (defined on paper) that enables us to reason about computation and to study the properties and limitations of computing

Question 4

How do we determine whether a string x is a member of a machine’s language L(M)?

Answer 4

• if M’s output is accept – which happens only if M is in an accept state when it reads the last symbol of string
  
  • i.e., the string must take M from start to final/accept state (machine ends on accept state after reading string)
• the string’s symbols must be over the machine’s alphabet Σ

Question 5

What is the formal definition of a FA?

Answer 5

A finite automaton is a 5-tuple (𝑄, Σ, 𝛿, 𝑞_𝑜, 𝐹), where

1. 𝑄 is a finite set called the states
2. Σ is a finite set called the alphabet
3. 𝛿: 𝑄 × Σ → 𝑄 is the transition function
4. 𝑞𝑜 ∈ 𝑄 is the start state
5. 𝐹 ⊆ 𝑄 is the set of accept states (or final states)

Question 6

Is a FA allowed to have 0 accept states?

Answer 6

Yes.
(book p.35)

Question 7

T or F:
“FA must have exactly one transition exiting every state for each possible input symbol”

Answer 7

True
(book p.35)

Question 8

Using the transition function, show that if an automaton is in state x when it reads a 1, it then moves to state y.

Answer 8

δ( x, 1 ) = y

Question 9

Formally state why it’s possible to have FA with zero accept states.

Answer 9

• setting F (set of accept states) to be the empty set ∅ yields 0 accept states, which is allowable

Question 10

What can we say about a machine’s recognized language if it accepts no strings?

Answer 10

It recognizes one language: empty language ∅.

Question 11

What does it mean for a machine to recognize a language?

Answer 11

• The language recognized (or accepted) by a FA M contains all the input strings which can take M from the start to the final state

Question 12

What does it mean for a machine M to accept a string x?

Answer 12

• if M stops in a final state after reading string x, then M accepts x
• thus, x is a member of the language recognized by M, i.e., x ∈ L(M)

Question 13

Define what it means for a set A to be the language for a machine M.

Answer 13

If A is the set of all the strings a machine M accepts, then A is the language of the machine M, i.e., L(M)=A