Ask Question, Ask an Expert


Ask Computer Engineering Expert

Answer all the problems. 

problem1) Construct one Turing Machine for computing each of the following functions

(i)  f (m, n) = m*n, where ‘*’ denotes multiplication

(ii) f (m, n) = 891_Turing machine.jpg

problem2) Construct one grammer for each of the following languages

(a) {ambn: m

(b) {w ∈ {0,1}* w=wR}    

problem3) Show that each of the following functions is primitive recursive:

(i)  f (m, n)   = 4mn

(ii) f (m, n)   = (5n)2m

problem4) Define following concepts formally:

a) Kleene Closure of an alphabet set.

b) Finite Automata

c) Godel Number

d) Regular Expression

e) Primitive Recursive Function

f) Unsolvable Problem

g) Turing-Decidable Problem

h) Moore Automata

problem5) (i)  Construct the DFA (Deterministic Finite Automata) accepting following Set:

{w ∈ {a,b}*: w has the even number of a’s and odd number of b’s}    

(ii) Construct Turing Machine for the following languages:

1) {anbncn : n > 1}

2)  wwR : w is any string of 0’s and 1’s}

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M92364

Have any Question? 

Related Questions in Computer Engineering

Brt has an income of 133 and a utility function ux1 x2

Bart has an income of $133 and a utility function U(x1, x2) = 28x1/21+ x2. The price of good 1 is $2 and the price of good 2 is $1. How many units of good 1 and good 2 will Bart demand? As his income keeps increasing, ho ...

Find an articlenbsponlinenbspthat discusses faith

Find an article online that discusses faith, technology and the Third World. Do a search using the key words "faith", "technology", and "third world." Respond to the following questions using your article as a reference: ...

Describe the considerations that have to be taken when

Describe the considerations that have to be taken when writing an application designed to drive a database by more than one simultaneous user?

Create a sql server login named wpc-ch10-user with a

Create a SQL Server login named WPC-CH10-User, with a password of WPC-CH10- User+password. Create a WPC-CH10-PQ database user named WPC-CH10-DatabaseUser, which is linked to the WPC-CH10-User login. Assign WPC-CH10-Datab ...

This is an investment opportunity and investment will occur

This is an investment opportunity and investment will occur at time 0 and sales commence at time 1. Initial cost: $28M Unit sales: 400,000 This year's selling price per unit: $60 This year's variable cost per unit: $42 L ...

A key to the performance of the vsws resident set

A key to the performance of the VSWS resident set management policy is the value of Q. Experience has shown that, with a fixed value of Q for a process, there are considerable differences in page fault frequencies at var ...

Your corporation western technology inc wants to invest 100

Your corporation Western Technology, Inc. wants to invest $100, 000 in a short term security for one-year. It is your responsibility to research and recommend the best investment vehicle for the company. The current chec ...

A number of policies protect patients from faulty dangerous

A number of policies protect patients from faulty, dangerous, or unnecessary medicines, medical procedures, and services. Note one of these public policies and identify how it protects a patient group.

What is data mining in your answer address the followinga

What is data mining? In your answer, address the following: (a) Is it another hype? (b) Is it a simple transformation or application of technology developed from databases, statistics, machine learning, and pattern recog ...

Ed invests 68000 in certificates of deposit ie cds paying

Ed invests $68,000 in certificates of deposit (i.e., CDs) paying 1.75%. How much additional money does he need to invest in stocks that are expected to generate a return of 11.8% so that the average return on all of Ed's ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate