Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

Answer all the problems.

1) Define the following concepts formally:

(a) Finite Automata

(b) Non-Deterministic Finite Automata (NDFA)

(c) Kleene Closure of a set of expressions

(d) Regular Expression

(e) Regular Language

(f) Primitive Recursive Function

(g) Unsolvable Problem

(h) Turing Machine

(i) Universal Turing Machine

(j) Turing-Decidable Problem

(k) Moore Automata

(l) Context-free Language

(m) Pushdown Automata

(n) Halting Problem

(o) NP-Hard Problem

(p) Context-free Language                               

2) Show that language

    L = { ap : p is positive prime integer} is not regular    

3) Show that each of the following function is primitive recursive function.

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

(b) fib (n), where fib (n) is defined by

fib (0) = 0
fib (1) =  1
fib ( n + 2) = fib (n) + fib (n + 1) , n ≥ 0

4) Construct one grammer for each of the following languages

(a) { ai bj ck | i = 2 j or j = 2k }

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

5) Construct one Turing Machine for calculating each of the following

(a) Llanguage { 0n 1n : n ≥ 1 }

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

Computer Engineering, Engineering

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

Have any Question? 


Related Questions in Computer Engineering

Design a minimum bcd to 7-segment led display decoder

Design a minimum BCD to 7-segment LED display decoder circuit. The input is a 4-bit BCD value, and there are 7 outputs - one output for each segment of the 7-segment display. The circuit should generate the appropriate d ...

Have a project where i have to visit four places that

Have a project where I have to visit four places that embodies: Fear, Confusion, Joy, and something else in the form of the five senses( touch, vision, hearing, smell, taste). So just send me a bunch of Environment photo ...

Indonesias production function is yaka l1-a assume that a

Indonesia's production function is Y=AK^a L^(1-a). Assume that A (technology) = 1 and a = .33. Additionally, Indonesia's investment/savings rate is 10%. Indonesia has 50 units of capital per worker and a constant depreci ...

Write a segment of code that reads a string from the

Write a segment of code that reads a String from the keyboard andthen outputs each letter in the String twice. For example, if theinput String is "Welcome!" the code should output "WWeellccoommee!!" to the screen.

Finally the committee will need to propose policies on

Finally, the committee will need to propose policies on training and education for earthquake preparedness. Both the organization's employees and the public will need education and training for the earthquake preparednes ...

Forensics involves the investigation and documentation of a

Forensics involves the investigation and documentation of a given crime to provide evidence that is typically used for legal action. E-mail is extensively used in personal and business operations to communicate with indi ...

Present an example where data mining is crucial to the

Present an example where data mining is crucial to the success of a business. What data mining functionalities does this business need (e.g., think of the kinds of patterns that could be mined)? Can such patterns be gene ...

Read the following article on changes in spains wine

Read the following article on changes in Spain's wine industry: http://goo.gl/9fZKml then answer the following questions. a.) The article notes that Spanish and Italian wine were exported for the same price in 2000, but ...

Consider the execution shown in figure 208 in addition the

Consider the execution shown in Figure 20.8. In addition, the system crashes during recovery after writing two log records to stable storage and again after writing another two log records. 1. What is the value of the LS ...

What cost factors are considered when a new tool is

What cost factors are considered when a new tool is evaluated? Why is it required that the tool can be used even when the scale of your project goes up?

  • 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