Homework Answers
Add Answer to:
3. (8) Let L be the language accepted by the following finite state machine: q0 q1...
Find a regular expression for the language accepted by the following automata q0 q1 q3
Find a regular expression for the language accepted by the following automata q0 q1 q3
Consider the TM with Q = q0, q1, q2, f, S = {0,1}, G= (0,1,b} (∆...
Consider the TM with Q = q0, q1, q2, f, S = {0,1}, G= (0,1,b} (∆ for blank), initial state q0 and final state f, with transition defined below: (q0, 0) → (q1, 1, R); (q1,1) → (q2, 0, L); (q2, 1) →(q0,1,R); (q1, ∆) →(f, ∆, R) (a) Provide the execution trace of this machine on the input 011 (b) Describe the language accepted by the TM (c) Suppose the transition (q0, 0) → (q1, 1, R) is replaced...
3.(4 4+20-36 points Formal Definition of a Turing Machine (TM) ATM M is expressed as a...
3.(4 4+20-36 points Formal Definition of a Turing Machine (TM) ATM M is expressed as a 7-tuple (Q, T, B, ? ?, q0,B,F) where: . Q is a finite set of states T is the tape alphabet (symbols which can be written on Tape) .B is blank symbol (every cell is filled with B except input alphabet initially .2 is the input alphabet (symbols which are part of input alphabet) is a transition function which maps QxTQxTx (L, R :...
a) What language is accepted by the Turing machine d(%-a)-(%-a, R), d(%-a)-(9-a, R). (5) Design a...
a) What language is accepted by the Turing machine d(%-a)-(%-a, R), d(%-a)-(9-a, R). (5) Design a Turing machine that will accept language OL-L6.a) (6) Design a Turing machine that will calculate fx)-3x. You must show the representation of s and 3x on the tape of Turing machine when the calculation starts and ends, respectively Extra Questions (20 points) 1. Fill the proper words in the blank (1) Given alphabet Σ, a language on Σ isa (2) Given a grammar G,...
Describe, as precisely as possible, the language generated by each of the following regular expressions. The...
Describe, as precisely as possible, the language generated by each of the following regular expressions. The alphabet is {a, b} (1) (aaa)* b(bb)* (2) abab(ab)* (3) b (e U a) b (4) a(aa) (bb)* UE*baa
3. For each of the following languages, . State whether the language is finite or infinite....
3. For each of the following languages, . State whether the language is finite or infinite. . State whether the language is regular or nonregular. . If you claim the language is regular: give a DFA (graphical representation) that recog- nizes the language. . If you claim that the language is not regular, describe the intuition for why this is so. Consider the following languages (a) [8 marks] The language of 8 bit binary strings that begin and end with...
THEOREM 3.1 Let r be a regular expression. Then there exists some nondeteministic finite accepter that...
THEOREM 3.1 Let r be a regular expression. Then there exists some nondeteministic finite accepter that accepts L (r) Consequently, L () is a regular language. Proof: We begin with automata that accept the languages for the simple regular expressions ø, 2, and a E . These are shown in Figure 3.1(a), (b), and (c), respectively. Assume now that we have automata M (r) and M (r) that accept languages denoted by regular expressions ri and r respectively. We need...
1. Consider the alphabet {a,b,c}. Construct a finite automaton that accepts the language described by the...
1. Consider the alphabet {a,b,c}. Construct a finite automaton that accepts the language described by the following regular expression. 6* (ab U bc)(aa)* ccb* Which of the following strings are in the language: bccc, babbcaacc, cbcaaaaccbb, and bbbbaaaaccccbbb (Give reasons for why the string are or are not in the language). 2. Let G be a context free grammar in Chomsky normal form. Let w be a string produced by that grammar with W = n 1. Prove that the...
1. Construct a DFSM to accept the language: L w E ab): w contains at least 3 as and no more than 3 bs) 2. Let E (acgt a...
1. Construct a DFSM to accept the language: L w E ab): w contains at least 3 as and no more than 3 bs) 2. Let E (acgt and let L be the language of strings consisting of repeated copies of the pairs at, ta, cg. ge. Construct both a DFSM to accept the language and a regular expression that represents the language. 3. Let ab. For a string w E , let w denote the string w with the...
Finite state machines & Regular Expressions Please select the best option 1. For the following questions...
Finite state machines & Regular Expressions
Please select the best option
1.
For the following questions Let r, s, t be regular expressions
for the same alphabet "á" (left column). Get the property on the
right side that produces equality for each regular expression.
2.
From the diagram of the solution M = (Σ, Q, s,, F) is
respectively:
e would be NONE.
3.
The following graph corresponds to a diagram of:
A. Transition machine and states
b. Transition...
Find a regular expression for the language accepted by the following automata q0 q1 q3
3.(4 4+20-36 points Formal Definition of a Turing Machine (TM) ATM M is expressed as a 7-tuple (Q, T, B, ? ?, q0,B,F) where: . Q is a finite set of states T is the tape alphabet (symbols which can be written on Tape) .B is blank symbol (every cell is filled with B except input alphabet initially .2 is the input alphabet (symbols which are part of input alphabet) is a transition function which maps QxTQxTx (L, R :...
a) What language is accepted by the Turing machine d(%-a)-(%-a, R), d(%-a)-(9-a, R). (5) Design a Turing machine that will accept language OL-L6.a) (6) Design a Turing machine that will calculate fx)-3x. You must show the representation of s and 3x on the tape of Turing machine when the calculation starts and ends, respectively Extra Questions (20 points) 1. Fill the proper words in the blank (1) Given alphabet Σ, a language on Σ isa (2) Given a grammar G,...
Describe, as precisely as possible, the language generated by each of the following regular expressions. The alphabet is {a, b} (1) (aaa)* b(bb)* (2) abab(ab)* (3) b (e U a) b (4) a(aa) (bb)* UE*baa
3. For each of the following languages, . State whether the language is finite or infinite. . State whether the language is regular or nonregular. . If you claim the language is regular: give a DFA (graphical representation) that recog- nizes the language. . If you claim that the language is not regular, describe the intuition for why this is so. Consider the following languages (a) [8 marks] The language of 8 bit binary strings that begin and end with...
THEOREM 3.1 Let r be a regular expression. Then there exists some nondeteministic finite accepter that accepts L (r) Consequently, L () is a regular language. Proof: We begin with automata that accept the languages for the simple regular expressions ø, 2, and a E . These are shown in Figure 3.1(a), (b), and (c), respectively. Assume now that we have automata M (r) and M (r) that accept languages denoted by regular expressions ri and r respectively. We need...
1. Consider the alphabet {a,b,c}. Construct a finite automaton that accepts the language described by the following regular expression. 6* (ab U bc)(aa)* ccb* Which of the following strings are in the language: bccc, babbcaacc, cbcaaaaccbb, and bbbbaaaaccccbbb (Give reasons for why the string are or are not in the language). 2. Let G be a context free grammar in Chomsky normal form. Let w be a string produced by that grammar with W = n 1. Prove that the...
1. Construct a DFSM to accept the language: L w E ab): w contains at least 3 as and no more than 3 bs) 2. Let E (acgt and let L be the language of strings consisting of repeated copies of the pairs at, ta, cg. ge. Construct both a DFSM to accept the language and a regular expression that represents the language. 3. Let ab. For a string w E , let w denote the string w with the...
Finite state machines & Regular Expressions
Please select the best option
1.
For the following questions Let r, s, t be regular expressions
for the same alphabet "á" (left column). Get the property on the
right side that produces equality for each regular expression.
2.
From the diagram of the solution M = (Σ, Q, s,, F) is
respectively:
e would be NONE.
3.
The following graph corresponds to a diagram of:
A. Transition machine and states
b. Transition...
Most questions answered within 3 hours.
-
Each row of the table below describes an aqueous solution at
25°C
.
The second column...
asked 10 seconds ago -
A horizontal wire is at y = 0. Current travels in the +x
direction. The magnetic...
asked 34 seconds ago -
Let X be a continuous random variable whose PDF is Let X be a
continuous random...
asked 21 minutes ago -
Martinez Company’s relevant range of production is 7,500 units
to 12,500 units. When it produces and...
asked 19 minutes ago -
A football with a mass of 1.2 kg is kicked from ground level to
a height...
asked 25 minutes ago -
Remember: Changes in supply determinants shift supply, and
changes in demand determinants shift demand. We say...
asked 24 minutes ago -
Why is the answer b), for this question? I came up with C) for
my incorrect...
asked 30 minutes ago -
Suppose that you know that in the population of full-time
employees in the United States, the...
asked 52 minutes ago -
This experiment was designed originally to sample various meat and carcass quality
aspects of Ontario pigs...
asked 52 minutes ago -
Dopamine Hydrochloride: draw the structure And Show the
functional groups in different colors and label the...
asked 44 minutes ago -
A rope supports a 10 kg dumbbell hanging from it. What is the
tension in the...
asked 44 minutes ago -
) Raw materials are studied for contamination. Suppose that
the number of particles of contamination per...
asked 1 hour ago