Scribd
Upload
4 views3 pages

Assignment 1

The document outlines an assignment for a course on the Theory of Automata, consisting of ten questions covering topics such as Kleene closure, regular expressions, finite automata design, NFA to DFA conversion, DFA minimization, and the differences between Mealy and Moore machines. Each question requires definitions, constructions, and conversions related to automata theory and grammar. The assignment aims to assess students' understanding of theoretical concepts and practical applications in computer science.

Uploaded by

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

Assignment 1

The document outlines an assignment for a course on the Theory of Automata, consisting of ten questions covering topics such as Kleene closure, regular expressions, finite automata design, NFA to DFA conversion, DFA minimization, and the differences between Mealy and Moore machines. Each question requires definitions, constructions, and conversions related to automata theory and grammar. The assignment aims to assess students' understanding of theoretical concepts and practical applications in computer science.

Uploaded by

tejasrajshobhitian
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Assignment 1

CSC-501 (Theory of Automata)


Attempt all questions
Questions
Q1.
a. Define Kleene closure. Illustrate the concept with an example involving a set Σ={a,b}\Sigma
= \{a, b\}Σ={a,b}.
b. Write a regular expression over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} that represents the language
of all strings containing at least one 0 and one 1.

Q2. Arithmetic Expressions and Regular Grammar

a. Define arithmetic expressions. Write a context-free grammar (CFG) for arithmetic expressions
consisting of digits, addition (+), and multiplication (*).
b. Convert the following arithmetic expression into postfix notation:
(3+4)∗(5+6)(3 + 4) * (5 + 6)(3+4)∗(5+6)

Q3. Design of Finite Automaton (FA)

Design a deterministic finite automaton (DFA) over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} that
accepts all binary strings that end with 01.

Q4. NFA to DFA Conversion (Subset Construction)

Given the NFA:

 States: Q={q0,q1}Q = \{q_0, q_1\}Q={q0,q1}


 Alphabet: Σ={a,b}\Sigma = \{a, b\}Σ={a,b}
 Transitions:
o δ(q0,a)={q0,q1}\delta(q_0, a) = \{q_0, q_1\}δ(q0,a)={q0,q1}
o δ(q0,b)={q0}\delta(q_0, b) = \{q_0\}δ(q0,b)={q0}
o δ(q1,b)={q1}\delta(q_1, b) = \{q_1\}δ(q1,b)={q1}
 Start state: q0q_0q0
 Final state: q1q_1q1

a. Construct the equivalent DFA.


b. Minimize the resulting DFA.

Q5. DFA Minimization (Optimization)

Minimize the following DFA:

States: {A,B,C,D,E,F}\{A, B, C, D, E, F\}{A,B,C,D,E,F}


Alphabet: {0,1}\{0, 1\}{0,1}
Start state: A
Final state: {E,F}\{E, F\}{E,F}
Transitions:

 A → 0 → B, A → 1 → C
 B → 0 → D, B → 1 → E
 C → 0 → F, C → 1 → A
 D → 0 → D, D → 1 → E
 E → 0 → F, E → 1 → E
 F → 0 → F, F → 1 → F

Q6. Mealy vs Moore Machine

a. Define Mealy and Moore machines with examples.


b. Construct a Moore machine equivalent to the following Mealy machine:

 States: {S0,S1}\{S_0, S_1\}{S0,S1}


 Input: {0,1}\{0, 1\}{0,1}
 Output: {X,Y}\{X, Y\}{X,Y}
 Transitions:
o δ(S0,0)=(S1,X)\delta(S_0, 0) = (S_1, X)δ(S0,0)=(S1,X)
o δ(S0,1)=(S0,Y)\delta(S_0, 1) = (S_0, Y)δ(S0,1)=(S0,Y)
o δ(S1,0)=(S0,X)\delta(S_1, 0) = (S_0, X)δ(S1,0)=(S0,X)
o δ(S1,1)=(S1,Y)\delta(S_1, 1) = (S_1, Y)δ(S1,1)=(S1,Y)

Q7. Construction of Mealy Machine from Moore Machine

Given the following Moore machine, convert it into an equivalent Mealy machine:
 States: {A,B}\{A, B\}{A,B}
 Input: {0,1}\{0, 1\}{0,1}
 Output function:
o λ(A)=0\lambda(A) = 0λ(A)=0
o λ(B)=1\lambda(B) = 1λ(B)=1
 Transitions:
o A→0→B
o A→1→A
o B→0→A
o B→1→B

Q8. Numerical: Design a DFA

Design a DFA over the alphabet Σ={a,b}\Sigma = \{a, b\}Σ={a,b} which accepts all strings in
which the number of a’s is divisible by 3.

Q9. Application and Limitation of Finite Automata

a. Discuss three practical applications of finite automata in computer science.


b. Explain two limitations of finite automata in language recognition.

Q10. Combination Question: FA with Output

Design a Mealy machine that takes a binary number as input (bit by bit from left to right) and
outputs 1 every time it detects an even number of 1s, else outputs 0.

You might also like