[go: up one dir, main page]
Scribd
Upload
9 views1 page

TCS Assignment

The document contains a series of assignments and questions related to the design of Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA) for various languages over the binary alphabet {0,1} and the alphabet {a,b}. It includes tasks such as drawing DFAs for specific conditions, writing regular expressions, and designing NFAs for strings with particular properties. Additionally, it requests a comparison of the differences between DFA and NFA.

Uploaded by

aryanthete21
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
9 views1 page

TCS Assignment

The document contains a series of assignments and questions related to the design of Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA) for various languages over the binary alphabet {0,1} and the alphabet {a,b}. It includes tasks such as drawing DFAs for specific conditions, writing regular expressions, and designing NFAs for strings with particular properties. Additionally, it requests a comparison of the differences between DFA and NFA.

Uploaded by

aryanthete21
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
You are on page 1/ 1

TCS Assignment-1 / Question bank for UT-1

1. Draw DFA which accepts the language over ∑= {0,1} for accepting all possible strings of 0s
and 1s not containing 101 as substring.
2. Draw DFA which accepts the language over ∑= {0,1}
A. All strings which have odd number of 1s and any number of 0s
B. All strings with exactly two 1s
C. All strings starting with 1 and length of string is divisible by 3
3. Draw DFA for the language containing strings in which leftmost symbol
differ from the rightmost symbol. ∑ = { a, b }
4. Design DFA which can accept a binary number which can divisible by 3
5. Draw a DFA over Σ = {0,1} that accepts all strings which do not contain two or more
consecutive 1s.
6. Write regular expression for the following languages.
A. The set {10, 1010}
B. The set {€, 0, 00, 000, . . .}
C. The set of strings over alphabet {0, 1} starting with 0.
D. The set of strings over alphabet {0, 1} ending in 1.
E. The set of strings over alphabet {a, b} starting with a and ending in b.
F. The set of all strings containing at least two 0’s.
G. The set of all strings which do not contain two or more consecutive 1s.
7. Design an NFA with ∑ = {0, 1} accepts all string ending with 01.
8. Design an NFA with ∑ = {0, 1} accepts all string in which the third
symbol from the right end is always 0.
9. Design an NFA with ∑ = {0, 1} accepts all strings in which the second
symbol from the right end is always 1. and convert it into DFA
10. List differences between DFA and NFA

You might also like