Question

In English, explain and contrast the terms “recognize” and “decide” as they relate to Turing Machines.

In English, explain and contrast the terms “recognize” and “decide” as they relate to Turing Machines.

Homework Answers

Answer #1

Recognize

Recognize in the Turing machine is for recpgnizing or identifing the language.

A turing machine recognises the language ,if it halts and accepts all strings in language

Decide

Decide in the Turing machine is for deciding the language

Turing machine decides the language if it halts and accepts on all strings in that language.

And it halts and rejects if it is not in that language

contrastion between Recognise and Decide

*Decider also halts if string is not in language

*But recognizer may halt or maynot halt halt in the string that are not in the language

*On all the inputs decider should halt either in accept or reject state

*On all inputs recognizer may or may not halt on strings that are not in language

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Write a Turing-machine style of algorithm to decide the language L2 given below. Use specific, precise,...
Write a Turing-machine style of algorithm to decide the language L2 given below. Use specific, precise, step-by-step English. So, describe how to test whether or not an input string is in the language L2 in finite time. No need to write a state diagram. L2 = {w : w has more a’s than it has b’s and c’s combined} over the alphabet Σ = {a, b, c}. Example strings: abaca ∈ L2. bcaa ∉ L2.
Write a Turing-machine style of algorithm to decide the language L1 given below. Use specific, precise,...
Write a Turing-machine style of algorithm to decide the language L1 given below. Use specific, precise, step-by-step English. So, describe how to test whether or not an input string is in the language L1 in finite time. No need to write a state diagram. L1 = {w : every ‘a’ within w is to the left of every ‘b’ within w} over the following alphabet Σ = {a, b, c}. In other words, you’re not allowed to have any ‘b’...
Define and explain the terms reasonable and prudent as they relate to standards of care.
Define and explain the terms reasonable and prudent as they relate to standards of care.
Provide a definition for both terms and explain how these two terms relate to each other....
Provide a definition for both terms and explain how these two terms relate to each other. 1. Signaling & Sorting 2. Returns to Education
Provide a definition for both terms and explain how these two terms relate to each other....
Provide a definition for both terms and explain how these two terms relate to each other. 1. Skill Biased Technicall Change an/or globalization 2. College Wage Premium
compare and contrast cell biology and biochemistry. how do they relate and how do they differ....
compare and contrast cell biology and biochemistry. how do they relate and how do they differ. explain
IN YOUR OWN WORDS, explain the following terms as they relate to the DNA structure and...
IN YOUR OWN WORDS, explain the following terms as they relate to the DNA structure and replication: 1. Antiparallel 2. Complementary base pairs 3. Template 4. S-phase
Research civil and criminal cases as they relate to computer forensics. Compare and contrast the types...
Research civil and criminal cases as they relate to computer forensics. Compare and contrast the types of evidence used to resolve these disputes, be sure to include both similarities and differences. Should standards be different depending upon the type of dispute - civil vs criminal? Explain
Instructions: Compare and contrast the terms contract and economic rents. Explain the concept of discounted cash...
Instructions: Compare and contrast the terms contract and economic rents. Explain the concept of discounted cash flow valuation and income capitalization rates. Using the internet, try to find at least five commercial properties for sale that would usually be valued with a very heavy weight for the income approach. Determine what type of information on income and expenses is provided. Can you find a web site with sufficient information to use the income related valuation techniques? If so, what is...
Contrast in detail the following terms: Species evenness and species richness. A)Be sure to define each,...
Contrast in detail the following terms: Species evenness and species richness. A)Be sure to define each, B)then explain how they are different and similar, and C)provide a theoretically example of how they are used when describing a community.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT