Ask Question, Ask an Expert


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

For this assignment you are a project manager your

For this assignment, you are a project manager. Your management has asked you to plan a project to develop an online shopping application to run on the newest model of the Blackberry smartphone. You know Blackberry has h ...

1 describe the scenario where none of philosophers ever

1. Describe the scenario where none of philosophers ever eats (i.e., starvation). What is the sequence of events that happen that lead up to this problem? 2. Describe how we can solve this problem by introducing the conc ...

Create a c program that computes the areas of rectangles

Create a C++ program that computes the areas of rectangles and tells the user which rectangle has the greatest area, or if the areas are the same. Create a C++ program that calculates the gross cost and net cost for call ...

We can design and build a postfix calculator that can be

We can design and build a postfix calculator that can be used to perform simple arithmetic operations. The calculator consists of a single storage component that consists of an operand stack. The operations performed by ...

Instructionsanswer all questions please show your working

Instructions Answer all questions. Please show your working for calculations. Formatting your assignment: - Please submit your assignment online as one document in PDF format. This format locks the information and is par ...

Create a cloud of turtles half of them one color and half

Create a " cloud " of turtles, half of them one color and half of them another color. Based on a probability have one color of turtles move up and the other color turtles move down. Label the turtles with their WHO numbe ...

Identifying purposes and characteristics of

Identifying Purposes and Characteristics of Processors Identifying Purposes and Characteristics of Memory How to Disassembling and Reassembling Laptops. How to Installing and Configuring Expansion Cards What are the diff ...

Cpsc programthis is the programwrite a class to represent a

CPSC Program This is the program Write a class to represent a dynamically sized array of integers. Name it DynArray. submit: a file named dynarray.h that contains all of your class code Class specifications: Private data ...

Alabama life and casualty insurance corporation specializes

Alabama Life and Casualty Insurance Corporation specializes in underwriting commercial farm policies throughout the southern United States. The company's chief information officer has become increasingly concerned that o ...

1 distinguish between multicasting and multiple unicasting2

1. Distinguish between multicasting and multiple unicasting. 2. When we send an e-mail to multiple recipients, are we are using multicasting or multiple unicasting? Give the reason for your answer. 3. Define which of the ...

  • 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

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro