Theory of Computation

Lab 1 (DFA)

• DFA for the language of string over {0.1} in which each string end with 11

• DFA accepting the string over {a,b} such that each string does not end with ab

• DFA for the language of string over {a,b} such that each string contain aba as substring

• DFA for the language of string over {0,1} such that each string start with 01

• DFA for the language of string over {0,1} such that set of all string ending in 00

• DFA for the language of string over {0,1} such that set of strings with 011 as a substring

Lab 2 (NFA)

• NFA that accepts string ending with 01

• NFA that accepts string containing substring 101

• NFA that accepts string starting with 10

Lab 3

• Program to find prefixes, suffixes and substrings from a given string

• Program to validate C identifiers and keywords