Part -1:

1. Construct finite automata, push down automata, Turing machines and regular expressions that models different types of languages.

2. Design various models of computation.

Question 1:

Give DFA's accepting the following languages over the alphabet {0,1}:

i. The set of all strings beginning with a 1 that, when interpreted as a binary integer, is a multiple of 5. For example, strings 101, 1010, and 1111 are in the language; 0, 100, and 111 are not.

ii. The set of all strings that, when interpreted in reverse as a binary integer, is divisible by 5. Examples of strings in the language are 0, 10011, 1001100, and 0101

iii. The set of all strings such that each block of five consecutive symbols contains at least two 0's.

iv. The set of all strings whose tenth symbol from the right end is a 1.

Question 2:

Informally describe the languages accepted by those following DFA's with transition tables (English words or sentence)

Note:
- All students should submit individual assignment.
- Copied assignments will not be marked.
- Late assignments will have negative markings.

Part -2:

Design various models of computation.

Question 1:

1. Prove that the followinglanguage are not regular Languages. Justify your answer by using pumping lemma for regular languages.
i. L = {0ⁿ 1 0ⁿ | n>0}.

ii. L = {0ⁿ 1²ⁿ | n>=1}.

Question 2:

i. Design context-free grammars for the language that contain the set {aⁱb^jc^k |i≠j or j≠k} that is the set of strings of a's followed by b's followed by c's, such that there are either a different number of a's and b's or a different number b's and c's, or both.

ii. The following grammar generates the language of regular expression 0*1(0+1)*:
S → A1B
A → 0A |?
B → 0B |1B|?
Give leftmost and rightmost derivations of the following strings:
a) 00101.
b) 1001.
c) 00011.