Construct a turing machine which encrypts passwords

Assignment Help Theory of Computation

Reference no: EM132548009

Read the caselet below and answer questions which follow:

Assume there is need to encryptpasswords using the Zn-Algorithm. The Zn-Algorithm takes an alphanumeric password and coverts it into a binary digit. The alphanumeric password must start with any letter from the alphabet A= {a-z} and must have exactly one digit from the alphabet D = {0-9}. The password must end with at least two characters from A. A password is encrypted by converting any consonant (C) character into a binary digit 0, any vowel (V) into a binary digit 1 and the digit into 2 in binary. For example if the input tap has a password ret7ure, it must output or write 01010101 on the tap after encryption.

Required

i. Construct a Turing machine which encrypts passwords using the Zn algorithm. Describe how the machine works.
ii. Design a DFA which accepts valid encrypted passwords.
iii. Design a PDA which accepts valid encrypted passwords.
iv. Give the grammar in Chomsky Normal Form which generates valid encrypted passwords.
v. Does your grammar allow LL(1) parsing? Why? Or Why Not?

Reference no: EM132548009

Questions Cloud

How the units completed are : A company haa 2000 units in beginning work in process, 30,000 units started in current period and 3000 units in ending work in process. The units completed are

Compute of bl net profit for the month of february : Limited is engaged in the manufacture,Based on optimum product mix, compute of BL's net profit for the month of February 2012

How many tests must be performed each year to breakeven : If the hospital charges $30 per test, how many tests must be performed each year to breakeven on the services? how much should be charged for each test

Show how the costs would be apportioned to each department : Show how the costs would be apportioned to each department? A factory has two production departments: preparation and assembly

Construct a turing machine which encrypts passwords : Construct a Turing machine which encrypts passwords using the Zn algorithm. Describe how the machine works - Design a DFA which accepts valid encrypted password

What was the total direct manufacturing cost variance : What was the total direct manufacturing cost variance for the firm's May production performance? Compute Material quantity variance cost

What are the impacts of disease on the individual : What are the impacts of disease on the individual, family, economy, society, nation, and the world?

Calculate kemper should establish a selling price of : To increase its profitability by $40,000, Kemper should establish a selling price of (Calculate). Calculate the minimum selling price it should set

Rest of the solar system formed : The oldest rocks on the surface of the Earth today date to approximately 4.2 billion years ago. The Earth and the solar system

User Account

All Pages