Advanced Discrete Mathematics-Ii

(i) The incidence matrix containing only two elements 0 and 1 is called :

(ii) A digraph in which for every edge (a, b), there is also an edge (b, a) is called :

(iii) Generating function for numeric function `a_r = α^r` is :

(iv) Solution of `a_r + 3a_r-1 = 0` is :

(v) A grammar contains only productions of the form `α → β`, where `|α| ≤ |β|` is called :

(vi) Length of string `α = a^2b^3a^b` is :

(vii) A finite state automata is a :

(viii) Let `M = < I, S, O, δ, λ >` be a finite state machine, then for some positive integer K, S is said to be K-equivalent to `S_j`, if `S_i ⇌ S_j ⇌ λ(S_i, x) = λ(S_j, x)` for all `x` such that :

(ix) A Moore machine is a six tuple `(I, Δ, δ, λ, S_0)` in which `λ` is :

(x) "The class of regular set over `Σ` is the smallest class R contained `Σ(α)` for every `a ∈ Σ` and closed under union, concatenation and closure" is known as :

(a) Cut-set matrix

(b) Path matrix

Find the adjacency matrix of the following graph :

Determine the discrete numeric function corresponding to the generating function `A(z) = 1 / (5 - 6z + z^2)`.

Find the homogeneous solution of the difference equation : `4a_r - 20 a_{r-1} + 17a_{r-2} - 4a_{r-3} = 0`.

(a) Phrase structure grammar

(b) Context-free grammar

Define terminal symbols and non-terminal symbols.

Define finite state automata.

Let `M = (S, I, O, f, g, S_0)` be a finite state machine, then prove that the relation 'K-equivalence on the set S of all states of M' is an equivalence relation.

Define reduced machine and regular expression.

Define Moore machine.

If A(G) is an incidence matrix of a connected graph G with n vertices, then prove that rank of A(G) is `n-1`.

If B is a circuit matrix of a connected graph G with e edges and n vertices, then prove that : `rank B = e - n + 1`.

Find the particular solution of the difference equation `a_r + 5a_{r-1} + 6a_{r-2} = 3r^2 - 2r + 1`.

Solve the recurrence relation : `a_r - 2 a_{r-1} + 3a_{r-2} - 4a_{r-3} + 2a_{r-4} = 0`.

Show that the language `L(G) = {a^n b^n c^n : n ≥ 1}` is generated by the grammar `G = < {S, B, C}, {a, b, c}, S, φ >`, where `φ` consists of the productions : `S→aSBC, S→aBC, cB→BC, aB→ab, bB→bb, bC→bc, cC→cc`.

Construct a grammar for the language : `L = {a^r b^s : r > s > 0}`.

Let S be any state in a finite-state machine and x and y are any words, then prove that : `δ(S, xy) = δ(δ(S, x), y)`.

Show that the following two machines `M_1` and `M_2` are equivalent :

M1

State	Input		Output
	1	2
A	B	C	0
B	C	D	0
F	D		0

M2

State	Next state		Output
	a = 0	a = 1
S1	S1	S2
S2	S1	S3
S3	S1	S3

State and prove Pumping lemma.

Construct a Mealy machine which is equivalent to the Moore machine given in the following table :

Present state	Next state		Output
	a = 0	a = 1
S1	S1	S2
S2	S1	S3
S3	S1	S3