Show that g is an encoding function

Assignment Help Data Structure & Algorithms

Reference no: EM132963378

Question 1: Consider the set1{A, B }^∗ of strings over the symbols A and B. Recall that is the empty string.

Define the relation g on {A, B}^∗× N such that

(, 0)∈g if ( s,n)∈g ( A.s, n × 100 + 12) ∈g

( B.s, n × 1000+ 1 22)∈g

(a) State the condition for g to be function and argue that g is indeed a function.

(b) State the condition for g to be one-to-one and argue that g is indeed one-to-one.

(d) Show that g is an encoding function for { A, B }^∗.

(e) Show that g is a Gödel numbering of { A, B }^∗

(f) Use g to give an enumeration of { A, B }^∗.

(g) State whether { A, B }^∗ is finite or infinite and whether it is countable or uncountable. Justify your answer.

(h) Consider the set { A, B, C }^∗ of strings over the symbols A, B and C. Give a Gödel numbering g of { A, B, C }^∗ such that for any string s, if s ∈ { A, B } ∗ then g( s) = g (s) .

(i) Is the set { A, B }^∗× { A, B, C }^∗ enumerable? Justify your answer.

Attachment:- Turing machine.rar

Reference no: EM132963378

Questions Cloud

Prepare a multi-step Income statement for Moon Corporation : Prepare a multi-step Income statement for Moon Corporation for 2020 using the below data - Advertising expense 250 Wages expense 3,300

Analyse the challenges organisations face accessing finance : Analyse the challenges organisations face accessing finance Challenges may include but are not limited to organisational size and strategic intent

What final payment will be necessary : A consumer buys goods worth $190. She pays $19 down and will pay $95 at the end of 1 year. What final payment will be necessary

How much can he withdraw at the end of each year : How much can he withdraw at the end of each year for the next 26 years if a 4.8% interest rate can be earned annually on the account's remaining balance

Show that g is an encoding function : State whether { A, B }* is finite or infinite and whether it is countable or uncountable and State the condition for g to be function and argue that g is indeed

Calculate the Total Manufacturing Costs : At a given level of Production, Biscuit Manufacturing has the following costs: Prime Costs $900,000. Calculate the Total Manufacturing Costs

Compute the net income : Profit recognition entries at year-end on the initial franchise fees under each of the following; Compute for the net income in 2020

Calculate the total raw material variance for May : Calculate the total raw material variance for May and break it down into sub-variances. How do you interpret the results of your calculations

How can management address those challenges : How can management address those challenges? What are the challenges associated with establishing fair values

User Account

All Pages