Discrete Structure 2069

Attempt all questions:

Group A (10x2=20)

1. Given propositions p and q, define conjunction and disjunction of p and q.

2. Is the following argument valid?

If taxes are lowered, then income rises.

3. Use mathematical induction to prove that 4ⁿ- 1 is divisible by 3.

4. State and prove “the pigeonhole principle”.

5. Develop a “general explicit formula” for a nonhomogeneous recurrence relation of the form: a_n = rq_n-1 +s, where s and r are constants.

6. Define the terms a language over a regular grammar and a regular expression.

7. Distinguish between multi graph and pseudo graph with suitable examples.

8. Let A = {0, 1}. Show that the following expressions are all regular expressions over A

a) 0* (0v1)*     b) 00* (0v1)* 1.

9. Distinguish between undirected and directed graphs with illustrations.

10. Explain non-deterministic finite state automata.

Group B (5x4=20)

11. Let S = {0, 1}. Give the regular expression corresponding to the regular set given:

a) {00, 010, 0110, 011110, ...}

b) {0, 001, 000, 00001, 00000, 0000001, ...}

12. For the Fibonacci sequence, prove that for n ≥ 2.

f²_n+1 − fn² =  f_n−1 f_n−2

13. Define explicit formula for the sequence: {a1, a2, a3,....}. Write an explicit formula for the sequence 2, 5, 7, 12, 19, 31.

14. Explain the rules of inference for quantified statements.

15. Define isomorphism. Given an example to show that the graphs are not isomorphic.

Group C (5x8=40)

16. Define deterministic finite state automata. When are two finite state automata equivalent? Explain it.

17. Construct the state transition table of the finite state machine whose diagram is shown:

18. Construct truth tables to determine whether the given statement is a tautology, a contingency, or an absurdity:

a) p ⇒ (q ⇒p)

b) q ⇒ (q ⇒p)

c) p ∧ ~ p

19. A phrase structure grammar g is defined to be a 4-tuple (V, S, v₀ |→ ), where V=(v_o, w, a, b, c}, S={a, b, c}, v_o |→ aw, w |→ bbw, w |→ c. Derive a sentence of L(G), the language of this grammar.

OR

Prove that an undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

20. Explain the concept of network flows and Max-flow Min-cut theorem with suitable examples.

OR

Find a maximum flow in the network shown in the figure.