CSIT_Labs

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