Deck 13: A: Modeling Computation

Question 1

.

Answer 1

Question 2

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

Answer 2

A∗ consists of all strings of 0's and 1's, including the empty string.

Question 3

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of

Answer 3

Question 4

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 0011.

Question 5

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 01.

Question 6

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 011111.

Question 7

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, a a} .

Question 8

Suppose a phrase-structure grammar has productions S → S11, S → 0A, S → A1, A → 0. Find a derivation of 01.

Question 9

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

Question 10

Find a production of the form "A → " such that S → 1S , S → 0A, A → produces {1n00 | n ≥ 0}.

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 P=
are derivable from S ?
(1) ba ,
(2) ab ,
(3) baab,
(4) aababa,
(5) aba

Question 12

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of

Question 13

Find a set of two productions that produces

Question 14

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, b, b a, b a a} .

Question 15

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 P=
are derivable from A ?
(1) babaa,
(2) aab ,
(3) bba

Question 16

Suppose a phrase-structure grammar has productions S → 1S0, S → 0A, A → 0. Find a derivation of 00.

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 P= - Which of these are derivable from ABa?
(1) ba ,
(2) abb ,
(3) aba ,
(4) b ,
(5) aababa

Question 18

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 0100.

Question 19

Suppose a phrase-structure grammar has productions S → S0, S → A1, A → 0. Find a derivation of 010.

Question 20

Find a production of the form "A → " such that S → 0A, A → produces {00}.

Question 21

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

Question 22

let resulting grammar G is

Question 23

let resulting grammar G is

Question 24

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

Question 25

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

Question 26

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

Question 27

What language is generated by the phrase-structure grammar if the productions are where is the start symbol?

Question 28

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 29

determine the output for each input string, using
10111

Question 30

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

Question 31

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

Question 32

determine the output for each input string, using
11000

Question 33

let resulting grammar G is

Question 34

Find a grammar for the set

Question 35

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

Question 36

Find the set recognized by this deterministic finite-state machine.

Question 37

determine the output for each input string, using
000

Question 38

let resulting grammar G is

Question 39

determine the output for each input string, using
1111

Question 40

let resulting grammar G is

Question 41

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

Question 42

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

Question 43

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

Question 44

Find the Kleene closure of A={1} .

Question 45

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

Question 46

Determine if 1101 belongs to the regular set 1(10)*1*.

Question 47

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

Question 48

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

Question 49

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 50

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

Question 51

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

Question 52

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

Question 53

Find the Kleene closure of A={00} .

Question 54

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

Question 55

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

Question 56

Determine if 1101 belongs to the regular set (11)*0*(11)*.

Question 57

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

Question 58

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 59

Determine if 1101 belongs to the regular set (01)*(11)*(01)*.

Question 60

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

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

Construct a Turing machine that computes

Question 63

Construct a Turing machine that computes

Question 64

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 65

Consider the Turing machine T :

Question 66

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

Question 67

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