Deck 13: Modeling Computation

Question 1

Construct a finite-state machine that models a vending machine accepting only quarters that gives a container of orange juice when 50 cents has been deposited, followed by a button being pushed. (The possible inputs are quarters and the button, and the possible outputs are nothing, orange juice, and a quarter. The machine returns any extra quarters.)

Answer 1

The following finite-state machine models the vending machine.

Question 2

What is the language generated by the grammar with productions where S is the start symbol?

Answer 2

The language is the set of all strings that consist of a 0 followed by an arbitrary number of 1's (possibly none).

Question 3

Suppose that A = {1, 11, 01} and B = {0, 10}. Find AB and BA.

Answer 3

We find that AB = {10, 110, 1110, 010, 0110} and BA = {01, 011, 001, 101, 1011, 1001}.

Question 4

Which strings belong to the set represented by the regular expression

Question 5

Find a deterministic finite-state automaton equivalent to the nondeterministic finite-state machine shown.

Question 6

What language is generated by the phrase-structure grammar if the productions are S → S11, S → λ where S is the start symbol?

Question 7

Construct a finite-state automaton that recognizes the set represented by the regular expression 10∗.

Question 8

What is the output produced by the following finite-state automaton when the input string is 11101?

Question 9

Which strings belong to the regular set represented by the regular expression (1∗01∗0)∗?

Question 10

Find a grammar for the set

Question 11

The productions of a phrase-structure grammar are S → S1, S → 0A, and A → 1. Find a derivation of 0111.

Question 12

Construct a finite-state machine with output that produces a 1 if and only if the last three input bits read are all 0s.

Question 13

Let A = {1, 10}. Which strings belong to A∗?

Question 14

Let A = {1, 10}. Describe the elements of A∗.