Scribd
Upload
23 views5 pages

1.turing Machine Which Encrypts Passwords Using The Z Algorithm

The document outlines a Turing machine designed to encrypt passwords using the Zn algorithm, detailing its operational states and character sets. It also describes a Deterministic Finite Automaton (DFA) and a Pushdown Automaton (PDA) that accept valid encrypted passwords, along with a context-free grammar in Chomsky Normal Form for generating such passwords. Additionally, it confirms that the grammar allows for LL(1) parsing due to its left non-terminal production rules.

Uploaded by

Kelvin Chisanga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
23 views5 pages

1.turing Machine Which Encrypts Passwords Using The Z Algorithm

The document outlines a Turing machine designed to encrypt passwords using the Zn algorithm, detailing its operational states and character sets. It also describes a Deterministic Finite Automaton (DFA) and a Pushdown Automaton (PDA) that accept valid encrypted passwords, along with a context-free grammar in Chomsky Normal Form for generating such passwords. Additionally, it confirms that the grammar allows for LL(1) parsing due to its left non-terminal production rules.

Uploaded by

Kelvin Chisanga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Kelvin Chisanga

R166760C
HBSCT 4.2
TOC Assignment 2

1.Turing machine which encrypts passwords using the Zn algorithm

Key

Let V={a,e,i,o,u}
Let C={a-z excepts V}
Let D={0,9}

How it Works

 From the initial point if the tape head reads symbol from V it prints 1 or else if read
character from C it prints 0 and move to the right ,else if not read any value from C
and V reject
 In state 2, if read character from set V print 1,move to the right or if any other
character from C is read print 0,move to the right. Accepts iteration
 From state 2 if digit from set D is read, print 10 and move to state 3
 From state 3 either a character from set V or C is read, print 1 and 0 respectively,
move to the right.
 Repeat the previous step once more, if read any value not from V and C, reject
 The machine checks if there are any other characters from V and C printing 1 and 0
respectively. Until the head reads Δ and goes to halt state hence accepted

ii.DFA which accepts valid encrypted passwords

.
iii.PDA which accepts valid encrypted passwords.

PART (iv)

Grammar in Chomsky Normal Form which generates valid encrypted passwords.

Regular Expression for Valid Password is

(0+1)(0+1)*10(0+1)(0+1)(0+1)
First convert to Context Free Grammar
S →WXYZ
W→0|1
X→0X|1X|^
Y→10
Z→AAB
A→0|1
B→0B|1B|^
CFG to Chomsky Grammar
1. Elimination of ^ ------
Nullables are X and B
S→WXYZ|WYZ
W→0|1
X→0X|1X|0|1
Y→10
Z→AAB|AA
A→0|1
B→0B|1B|0|1
2. Eliminate unit production ----in this case no unit productions
3. Separate terminals from no terminals
S→WXYZ|WYZ
W→0|1
Y→10
X→TX|UX|0|1
Z→AAB|AA
A→0|1
B→TB|UB|0|1
T→0
U→1
4. The Chomsky Normal Form after Remove long rules
S→R1R2|WR2
R2→YZ
R1→WX
W→0|1
X→TX|UX|0|1
Y→10
Z→R3B|AA
R3→AA
A→0|1
B→0B|1B|0|
v.Yes it allow LL(1) parsing because production rules are applied from left non terminal symbols in
the structure of the string and scan to determine the production rule to use looking ahead in the
grammar

You might also like