Scribd
Upload
29 views1 page

Unit1 Assignment1

The document is an assignment sheet for a course on Formal Languages and Automata, consisting of five questions related to ten defined languages. Students are required to describe the languages, provide examples of valid and invalid strings, and construct both deterministic and non-deterministic finite automata for each language. Additionally, students must convert given NFAs into DFAs.

Uploaded by

shivamjakhar003
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
29 views1 page

Unit1 Assignment1

The document is an assignment sheet for a course on Formal Languages and Automata, consisting of five questions related to ten defined languages. Students are required to describe the languages, provide examples of valid and invalid strings, and construct both deterministic and non-deterministic finite automata for each language. Additionally, students must convert given NFAs into DFAs.

Uploaded by

shivamjakhar003
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

21CSC301T: Formal Languages and Automata

Assignment Sheet - 1
Question 1

Write in your own words what does the following TEN languages represent? Give two examples each for valid
and invalid strings.

Example: L3 = {awb : w over {a,b}}


Answer: Set of strings over {a,b} that start with a and end with b.
Two Valid Strings: abb, abbab, …
Two invalid Strings: ababa, afhfb

L1 = {w | over {0,1} and |w| = 0 mod 3} L6 = {w010 | w over {0,1}}


L2 = {w | w over {0,1} and |w| = 1 mod 2} L7 = {u01v | u,v over {0,1}}
L3 = {awb : w over {a,b}} L8 = {w over {0,1} | w is a binary string divisible by 4}
L4 = {anbm : n > 0, m > 1} L9 = {w over {0,1,2, .. 9} | w (as a number) is divisible by 3}
L5 = {aabw | w over {a,b}} L10 = {w | w over {0,1} and |w|1 = 0 mod 2}

Question 2

For each of the above TEN languages (L1-L10, in general say L), state (in standard form) what is LR, LC, L*
(wherever possible)

Question 3

For each of the above TEN languages, construct a deterministic finite automaton (DFA).

Question 4

For each of the above TEN languages, construct a non-deterministic finite automaton (NFA). Convert your
constructed NFA into DFA.

Question 5

Convert each of the following NFA into DFA.

You might also like