Deck 13: Modeling Computation

Question 1

Suppose a phrase-structure grammar has productions of 011111.

Answer 1

Question 2

Let G be the phrase-structure grammar with vocabulary V={A, B, 0,1, S} , terminal elements T={0,1} , start symbol S , productions
from S ?
(1) 000 ,
(2) 11 ,
(3) 010 ,
(4) 0000 ,
(5) 0001
(6) 110 ,
(7) 0010 .

Answer 2

(3),(7)

Question 3

Suppose a phrase-structure grammar has productions Find a derivation of 1000 .

Answer 3

Question 4

Suppose a phrase-structure grammar has productions Find a derivation of 0011 .

Question 5

Suppose a phrase-structure grammar has productions Find a derivation of 01

Question 6

Suppose A = {0, 1}. Describe all strings belonging to A∗.

Question 7

Find a set of two productions that produces

Question 8

Suppose V={S, A, a, b}, T={a, b} , and S is the start symbol. Find a set of productions that includes and generates the language {a, b, ba, baa} .

Question 9

Suppose a phrase-structure grammar has productions Find a derivation of 0100 .

Question 10

Suppose V={S, A, a, b}, T={a, b} , and S is the start symbol. Find a set of productions that includes and and generates the language {a, aa} .

Question 11

Let G be the phrase-structure grammar with vocabulary V={A, B, a, b, S} , terminal element set T={a, b} , start symbol S , and production set
derivable from S?
(1) ba ,
(2) ab ,
(3) baab,
(4) aababa,
(5) aba .

Question 12

Let G be the phrase-structure grammar with vocabulary V={A, B, a, b, S} , terminal element set T={a, b} , start symbol S , and production set
derivable from ABa?
(1) ba ,
(2) abb ,
(3) aba ,
(4) b ,
(5) aababa.

Question 13

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

Question 14

Suppose a phrase-structure grammar has productions
Find a derivation of 110000 .

Question 15

Find a production of the form such that produces {00} .

Question 16

Suppose a phrase-structure grammar has productions Finf a derivation of 01 .

Question 17

Let G be the phrase-structure grammar with vocabulary V={A, B, a, b, S} , terminal element set T={a, b} start symbol S , and production set
derivable from A ?
(1) babaa,
(2) aab ,
(3) bba .

Question 18

Find a production of the form such that produces

Question 19

Suppose a phrase-structure grammar has productions Find a derivation of 00 .

Question 20

Suppose a phrase-structure grammar has productions
Find a derivation of 010 .

Question 21

What is the language generated by the grammar with productions S → SA, S → 0, A → 1A,and A → 1, where S is the start symbol?

Question 22

Question 23

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

Question 24

Question 25

Question 26

What is the output produced by this finite-state machine when the input string is 11101?

Question 27

Question 28

Question 29

Question 30

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

Question 31

In questions determine the output for
each input string, using this state table.

Question 32

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

Question 33

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.)

Question 34

In questions determine the output for

Question 35

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

Question 36

Question 37

Question 38

In questions determine the output for

Question 39

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

Question 40

In questions determine the output for

Question 41

Determine if 1101 belongs to the regular set .

Question 42

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

Question 43

Find all strings recognized by this deterministic finite-state automaton.

Question 44

Determine if 1101 belongs to the regular set

Question 45

Find the Kleene closure of A = {00}.

Question 46

Find the language recognized by this nondeterministic finite-state automaton.

Question 47

Which strings belong to the regular set represented by the regular expression

Question 48

Find the language recognized by this nondeterministic finite-state automaton.

Question 49

Let A={0,11} . Find A³ .

Question 50

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

Question 51

Find all strings recognized by this deterministic finite-state automaton.

Question 52

Which strings belong to the set represented by the regular expression 0∗ ∪ 11?

Question 53

Determine if 1101 belongs to the regular set 1*0*1 .

Question 54

Determine if 1101 belongs to the regular set .

Question 55

Find the Kleene closure of A = {0, 1, 2}.

Question 56

Determine if 1101 belongs to the regular set .

Question 57

Construct a finite-state automaton that recognizes all strings that end with 11.

Question 58

Let A={0,11} . Find A²

Question 59

Determine if 1101 belongs to the regular set .

Question 60

Find the Kleene closure of A={1} .

Question 61

For the following Turing machine T, find the final tape when T is run on the following tape, beginning in the
initial position (the first nonzero entry from the left):

Question 62

For the following Turing machines T, find the final tape when T is run on the following tape, beginning in the
initial position (the first nonzero entry from the left):

Question 63

Which strings are recognized by the following finite-state automaton?

Question 64

Consider the Turing machine
For the following tape, determine the final tape when T halts, assuming that T begins in state s₀ at the leftmost nonblank symbol.

Question 65

Construct a Turing machine that computes where

Question 66

Determine if 1101 belongs to the regular set .

Question 67

Construct a Turing machine that computes where

Question 68

nonblank symbol.

Question 69

For the following Turing machine T, find the final tape when T is run on the following tape, beginning in the
initial position (the first nonzero entry from the left):

Question 70

For the following Turing machine T, find the final tape when T is run on the following tape, beginning in the
initial position (the first nonzero entry from the left):

Question 71

Consider the Turing machine
For the following tape, determine the final tape when T halts, assuming that T begins in state s₀ at the leftmost nonblank symbol.