Select Page

Subject: Physics    / General Physics
Question

1. Create a state diagram for the finite automation whose state table is shown below. S0 is the start state and S3 is the only final state.

State

Input

a

b

c

d

S0

S1

S1

S2

S0

S1

S2

S0

S1

S1

S2

S1

S0

S3

S3

S3

S3

S3

S1

S2

2. Create finite automata with the following characteristics. Clearly label the states and transitions. Indicate the starting state and any final states. In each case, indicate the transition function using both a state table and a state diagram. Each automation will accept input strings of 0s and 1s.

a. Create a finite automation that recognizes any string with an even number of 1s.

b. Create a finite automation that recognizes any input string that contains two 0s as the final characters.

3. Two middle school students have devised a clever code for passing notes during class. The code ensures the privacy of their communications if the teacher intercepts a note. The code works by using every third letter in the message to carry the real content. The punctuation is to be ignored. The true message starts with the first letter in the note. For example, the note might read

Ice milk of vase I aim rateterhe.

The secret message is “I love math”.

a. design a finite-state machine with output that decodes these secret messages.

b. Suppose the code is changed so that all letters up to and including the first lowercase “e” are ignored. The next letter, and every third letter thereafter, will constitute the secret message. Modify the finite-state machine in part (a) to decode these new messages.

4. Let= 0,1 , = , , , and = ? 01 | 1, ? 0 | 1, ? 00 | 1

and let S be the start symbol. Which of the following strings are derivable from S? If the string can be derived, show a derivation; otherwise give some reason why it cannot.

a. 011

b. 10110

c. 010001

d. 01010

5. Let ? = {0, 1, ?}. Create a regular grammar that generates each of the following languages.

a.= 01 | ? 1

b. = 001 00 | ? 2

6. Prove that if A and B are sets of strings, then

? = ?

Order Now