Discrete Structures - Unit Wise Questions
1. Define disjunction and conjunction with suitable examples.
2. Consider a set U = { 1,2,3,4,5,6,7,8,9,10}. What will be the computer representation for set containing the numbers which are multiple of 3 not exceeding 6? Describe injective, surjective and bijective function with examples.
4. Prove that 
by using set builder notation. How sets are represented by using bit string? Why it is preferred over unordered representation of sets?
5. How can you relate domain and co-domain of functions with functions in programming language? Discuss composite and inverse of function with suitable examples.
6. Which of the following are posets?
12. Define ceiling and floor function. Why do we need Inclusion - Exclusion principle? Make it clear withsuitable example.
1. Why breaking down of large integer into set of small integers is preferred while performing integer arithmetic? Find sum of numbers 123,684 and 413,456 by representing the numbers as 4-tuple by using reminders modulo of pair-wise relatively prime numbers less than 100.
2. Find the value of x such that x = 1 (mod 3), x = 1 (mod 4), x = 1 (mod 5) and x = 0 (mod 7) using Chinese remainder theorem.
6. State Euclidean and extended Euclidean theorem. Write down extended Euclidean algorithm and illustrate it with example.
5. Find the value of x such that x = 1 (mod 5) and x = 2 (mod 7) using Chinese remainder theorem.
11. Define zero-one matrix. Explain the types of function. [1+4]
9. What does primality testing means? Describe how Fermat's Little Theorem tests for a prime number with suitable example.
1. Show that the implication and its contrapositive are logically equivalent.
1. Define the term converse, contropositive and inverse.
2. Which rule of inference is used in the following argument?
If I work all night on this homework, then I can answer all the exercise. IF answer
all the exercise, I will understand all the material. Therefore, if I work all night on
this homework, then I will understand the material.
2. State division and remainder algorithm. Suppose that the domain of the propositional function P(x) consists of the integers 0, 1, 2, 3 and 4. Write out each of following propositions using disjunctions, conjunctions and negations. [4+6]
a. ∃x P(x)
b. ∀x P(x)
c. ∃x ¬P(x)
d. ∀x ¬P(x)
e. ¬∃x P(x)
f. ¬∀x P(x)
1. What is conjunction? Discuss with suitable example and truth table.
1. What is negation? Discuss with suitable example and truth table.
1. What is compound proposition? Discuss implication with suitable example.
1. Given propositions p and q, define conjunction and disjunction of p and q.
1. What do you mean by proposition? Give example to justify your answer.
1. Given propositions p and q, define conjunction and disjunction of them.
1. Define proposition and its negation with an example.
2. Is the following argument valid? If Socrates is human, then Socrates is mortal Socrates is human.
∴ Socrates is mortal.
2. Define existential quantifications with suitable examples.
2. Show that 
and 
are logically equivalent.
2. How do you define logically equivalent propositions?
2. Is the following argument valid?
Smoking is healthy.
If smoking is healthy, then cigarettes are prescribed by physicians.
∴Cigarettes are prescribed by physicians
2. Is the following argument valid?
If taxes are lowered, then income rises.
2. Which rule of inference is used in the following argument?
Ram is hard working. If Ram is hard working, then he is intelligent. Therefore Ram is intelligent.
2. Discuss universal quantifier with example.
2. Show that (p∧q ) → p is a tautology by using truth table.
3. What is valid argument?
3. State the rules for the strong form of mathematical induction with propositions.
3. Define universal instantiation.
3. State which rule of inference is basis of the following argument: “It is below freezing and raining now, therefore, it is below freezing now.”
3. State which rule of inference is the basis of the following argument; “It is below freezing now. Therefore, it is either below freezing or raining now.”
3. Give examples of addition rule and simplification rule of inference.
6. Prove that if n is positive integer, then n is odd if and only if 5n+6 is odd. [5]
7. Define proposition. Consider the argument "John, a student in this class knows how to write program in C. Everyone who knows how to write program in C can get a high paying job. Therefore, someone in this class can get high paying job." Now, explain which rules of inferences are used for each step. [1+4]
8. Represent the argument “If it does not rain or if is not foggy then the sailing race will be held and the lifesaving demonstration will go on. If sailing race is held then trophy will be awarded. The trophy was not awarded. Therefore it not rained” in propositional logic and prove the conclusion by using rules of inferences.
9. Discuss common mistakes in proof briefly. Show that n is even if n3+5 is odd by using indirect proof.
5. All over smart people are stupid. Children of stupid people are naughty. John is a children of Jane. Jane is over smart. Represent these statements in FOPL and prove that John is naughty.
7. Let A = "Aldo is Italian" and B = "Bob is English". Formalize the following sentences in proposition.
a. Aldo isn't Italian.
b. Aldo is Italian while Bob is English.
c. If Aldo is Italian then Bob Bob is not English.
d. Aldo is Italian or if Aldo isn't Italian then Bob is English.
e. Either Aldo is Italian and Bob is English, or neither Aldo is Italian nor Bob is English.
11. What is logical equivalence? Show that p→q and ¬q → ¬q are logically equivalent.
OR
Discuss Modus Ponens with suitable example.
11. Express the statement " Everyone has exactly one best friend " as a logical expression involving predicates, quantifiers with a domain consisiting of all people and logical connectives.
11. Explain the 4 rules of inference for quantified statements.
11. Explain the rules of inference for quantified statements.
11. Explain the 2 rules of inference for quantified statements and give suitable examples.
OR
Show that the propositions pV( p ᴧ r ) and ( rV q) ᴧ ( p V r) are logically equivalent.
11. Differentiate between existential and universal quantifiers with suitable examples.
14. Explain the rules of inference for quantified statements.
12. Prove that the product xy is odd if and only if both x and y are odd integers .
16. Discuss direct =, indirect and vacuous proof with suitable example.
16. Discuss direct proof, indirect proof, and proof by contradiction with suitable example.
16. 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
OR
Explain the method of proving theorems by direct indirect, controdiction and by cases.
16. Discuss the different rules of inference for quantified statements along with suitable example of each.
16. Explain Tautologies, contradiction and contingencies with suitable examples.
OR
Explain the method of proving theorems by direct, indirect, contradiction and by cases.
16. Discuss the techniques of proofs by contradiction and by cases with suitable examples.
16. Discuss the techniques of direct proof indirect proof and vacuous proof for proving implications with suitable examples.
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
1. Prove that for all integers x and y, if x2+y2 is even then x+y is even. Using induction prove that 13+23+..........+n3 = n2(n+1)2/4. [5+5]
3. State the rule for the strong form of mathematical induction with prepositions.
3. Use mathematical induction to prove that 4n- 1 is divisible by 3.
3. Compute the following values.
a. 3 mod 4 b. 7 mod 5 c. -5 mod 3 d. 11 mod 5 e. -8 mod 6
Write down the recursive algorithm to find the value of bn and prove its correctness using induction.
4. Prove that for every positive integer n ≥ 1, n2+n is even integer using mathematical induction.
10. How mathematical induction differs from strong induction? Prove that 12+22+32+........+n2 = n(n+1)(2n+1)/6 by using strong induction.
6. Prove that 5n-1 is divisible by 4 using mathematical induction.
11. Write down recursive algorithm for computing an. Argue that your algorithm is correct by using induction.
12. Represent any three set operations using Venn diagram. Give a recursive defined function to find the factorial of any given positive integer. [3+2]
11. Use mathematical induction to prove that the sum of the first n odd positive integers is n2?
OR
Discuss Modus Ponens with suitable example.
12. Find an explicit formula for the Fibonacci numbers, with recursion relation fn−1 + fn−2 and f0 = 0 , f1 = 1
12. For the Fibonacci sequence, prove that for n ≥ 2.
f2n+1 − fn2 = fn−1 fn−2
13. Find an explicit formula for the Fibonacci sequence defined by
fn = fn−1 + fn−2 , f1 = f2 = 1
13. Define explicit formula for the sequence: {a1, a2, a3,....}. Write an explicit formula for the sequence 2, 5, 7, 12, 19, 31.
16. What is mathematical induction? Use mathematical induction to prove that1.1! + 2.2! + ... + n.n! = (n+1)! – 1, wherever n is a positive integer.
17. Find all the solutions of the recurrence relation an = 4an −1+n2 . Also find the solution of the relation with initial condition a1 =1.
2. Define linear homogeneous recurrence relation. Solve the recurrence relation an=an/2+n+1, with a1=1.Also discuss about probabilistic primility testing with example.
1. State pigeonhole principle. Solve the recurrence relation an = 3an-1 - 3an-2 + an-3 with initial conditions a0=1 ,a1 = 3, a2=7.
3. Use binomial coefficient in the expansion of (x + y)4.
3. What is the coefficient of x12 y13 in the expansion of (2x – 3y)25 ?
4. Determine whether the sequence {an} is solution of the recurrence relation an =2an−1 − an−2 where an = 3n.
4. State and prove “the pigeonhole principle”.
4. Is the sequence {an} a solution of the recurrence relation an = -3an-1 + 4an-2 if an = 2n?
4. How many different license plates is available if each plate contains sequence of three letters followed by three digits?
4. What is the coefficient of x7 in (1+x)11? Describe how relation can be represented using matrix. [2+3]
4. State and prove " the extended pigeonhole principle".
5. Define linear nonhomogeneous recurrence relation of degree k with coefficients.
4. In how many ways we can draw a heart or a diamond from an ordinary deck of playing cards?
4. State and prove the Pigeonhole principle.
4. State the Pigeonhole principle. How many students must be in class to guarantee that at least two students receive the same score on the final exam is graded on a scale from 0 to 100?
4. State and prove the Pigeonhole principle.
4. State and prove “the extended pigeonhole principle”.
5. Solve the recurrence relation an = 5nn-1 - 6nn-2 with initial conditions a0 =1, a1 = 4. [5]
5. Let {an} be a sequence that satisfies the recursion relation an = an-1 - an-2 for n≥2 and suppose that a0 = 3 and a1=5. Find the values a2 and a3.
5. Define linear homogeneous recurrence relation.
5. Define linear homogeneous recurrence relation of degree k with constant coefficients.
5. Develop a “general explicit formula” for a nonhomogeneous recurrence relation of the form: an = rqn-1 +s, where s and r are constants.
5. What is pigeonhole principle?
5. How many ways are there to select a first, second and third – prize winners from 10 different people?
5. How many students must be in a class to guarantee that at least two students receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points?
6. Define linear homogeneous recurrence relation.
7. State and prove generalized pigeonhole principle? How many cards should be selected from a deck of 52 cards to guarantee at least three cards of same suit?
8. Show that if there are 30 students in a class, then at least two have same names that begin with the same letter. Explain the Pascal's triangle. [2.5+2.5]
4. Solve the recurrence relation an = 5an-1 - 6an-2 with initial conditions a0 = 1 and a1 = 2.
11. State and prove pigeonhole principle. What is the minimum number of student required in a discrete mathematics class to be sure that at least six receive the same grade, if there are five possible grades A, B, C, D, and F?
11. How many bit strings of length eight either start with a 1 bit or end with two bits 00?
12. Discuss the importance of recurrence relation in the analysis pf divide – and – conquer algorithms.
12. Find the solution of the recursion relation an = an-1 + 2an-2 with a0 = 2 and a1=7?
OR
Find an explicit formula for the Fibonacci numbers.
12. Define the binomial coefficient and give the general term of the binomial coefficient. Show that the sum of the binomial coefficient is 2n.
9. How many 3 digits numbers can be formed from the digits 1,2,3,4 and 5 assuming that:
a. Repetitions of digits are allowed
b. Repetitions of digits are not allowed
12. Discuss the importance of recurrence relations in the analysis of divide-and-conquer algorithms.
12. What is binomial theorem? Use this theorem to find the coefficient of x12 y13 in the expansion of(2x – 3y)25.
12. Discuss the principles of inclusion-exclusion. How many bit strings of length eight either start with a 1 bit or end with two bits 00?
10. List any two applications of conditional probability. You have 9 families you would like to invite to a wedding. Unfortunately, you can only invite 6 families. How many different sets of invitations could you write?
17. Find the solution to the recurrence relation an = 6an−1 − 11an−2 + 6an−3 with the initial conditions a0 = 2, a1 = 5, and a2 = 15.
OR
Find the explicit formula for the Fibonacci numbers. Use fn = fn−1 + fn−2 as recursive condition and f0 = 0 and f1 = 1 as initial condition.
17. Define linear homogenous recurssion relation of degree k with constant coefficient with suitable examples. What is the solution of recurrence relation an = 6 an-1 - 9 an-2 with a0 = 1 and a1 = 6?
17. Describe linear homogeneous and linear non-homogeneous recurrence relations with suitable examples.
17. Define linear homogeneous recursion relation of degree K with constant coefficient with suitable examples. What
is the solution of the recurrence relation an = an−1 + 2an−2 with a0 = 2 and a1 = 7?
17. Find the solution to the recursion relationan = 6an-1 – 11an-2 + 6an-3 with initial conditions a0 = 2, a1 = 5 and a2 = 15.
OR
Suppose that a person deposits Rs.10,000/- in a fixed account at a bank yielding 11% per year with interest
compounded annually. How much will be in the account after 10 years? Solve the problem with modeling it into
recursion relations.
17. Solve the recurrence relation an = 2an-1 + 2an-2 + 2an-3 for n ≥ 3, a0 = 3, a1 = 6 and a2 = 9.
OR
Find the explicit formula for the Fibonacci numbers. Use fn = fn-1 + fn-2 as recursive condition and
f0 = 0 and f1 = 1 as initial condition.
18. Find the recurrence relation to find the number of moves needed to solve the TOH (Tower of Hanoi) problem with n disks. Discuss application of recurrence relation in divide-and-conquer algorithms.
3. List the necessary conditions for the graphs to be isomorphic with an example. Find the maximal flow from the node SOURCE to SINL in the following network flow. [5+5]
1. What is S-D cut? For the following network flow find the maximal flow from S to D.
3. How Zero-one matrix and diagraphs can be used to represent a relation? Explain the process of identifying whether the graph is reflexive, symmetric, or anti-symmetric by using matrix or diagraph with suitable example.
3. Define Eular circuit with suitable example. Find the maximal flow s to t from the given network flow.
6. Distinguish between binary tree and spanning tree with suitable examples.
6. Show that an undirected graph has an even number of vertices of odd degree.
6. Define cut vertices and cut edges.
7. Suppose that a planar simple graph has 20 vertices, each of degree 3. Into how many region does a representation of this planar graph split the plane?
7. What is minimum spanning tree?
8. What is bipartite graph?
7. Consider Kn, the complete graph on n vertices. What is the degree of each vertex?
7. Distinguish between multi graph and pseudo graph with suitable examples.
8. How many edges are there in graph with 10 vertices each of degree six?
8. Define the complete graph Kn on n vertices and the complete bipartile graph Km,n with suitable examples.
9. What is decision tree?
8. Define saturated edge in a transport network.
8. Verify the Handshaking theorem in the figure.
8. Distinguish between multigraph and pseudograph with suitable examples.
8. What is minimal cut?
8. What is chromatic number of a graph?
9. Illustrate the Dijkstra's Algorithm to find the shortest path from source node to destination node with an example. [5]
10.Define saturated and unsaturated edge?
9. Which of the undirected graphs in the following figure have an Euler circuit? Explain.
9. Distinguish between undirected and directed graphs with illustrations.
9. Is the graph K4 planar? How?
9. What is spanning tree?
9. Which of the undirected graphs in the following have an Euler path?
10. What are the significances of Minimal Spanning Tree? Describe how Kruskal's algorithm can be used to find the MST. [2+3]
10. State max-flow min-cut theorem.
10. What is the chromatic number of the complete bipartile graph Km,n , where m and n are positive integers?
10. What is regular graph ?
10. What is the chromatic number of the complete bipartite graph, where m and n are positive integers?
10. Determine the chromatic number Kn.
10. Determine the chromatic number Kn.
7. Define reflexive closure and symmetric closure. Find the remainder when 4x2 - x + 3 is divided by x + 2 using remainder theorem.
12. What is meant by chromatic number? How can you use graph coloring to schedule exams? Justify by using 10 subjects assuming that the pairs {(1,2), (1,5), (1,8), (2,4), (2,9), (2,7), (3,6), (3,7), (3,10), (4,8), (4,3), (4,10), (5,6), (5,7)} of subjects have common students.
8. Define Eular path and Hamilton path with examples. Draw the Hasse diagram for the divisible relation on the set { 1, 2, 5, 8, 16, 32} and find the maximal, minimal, greatest and least element if exist.
8. Define Eular path and Hamilton path. Give examples of both Eular and Hamilton path.
13. Show that K3,3 is not planar?
14. What is planar graph? Show that K3,3 is non-planar.
13. What is graph isomorphism? What are the different invariants of graph isomorphism?
10. What is minimum spannung tree? Explain Kruskal's algorithm for finding minimum spanning tree.
15. Prove that “a tree with n vertices has n-1 edges”.
14. Discuss adjacency matrix representation of graph with example.
14. Show that a tree with n vertices has n-1 edges.
14. Discuss adjacency matrix representation of a graph with suitable example.
14. Show that the graphs in the following figure are not isomorphic.
What can you say about the complexity of graph isomorphism algorithms in terms of complexity?
14. Prove that an undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.
14. Determine whether the graphs shown in the following figure are isomorphic.
What can you say about the graph isomorphism algorithms in terms of efficiency?
11. Define spanning tree and minimum spanning tree. Mention the conditions for two graphs for being isomorphic with an example.
11. List any two applications of graph coloring theorem. Prove that "A tree with n vertices has n-1 edges"
14. When does the two simple graphs G1 = m(V1, E1) and G2(V2, E2) are isomorphic. Show that the graph G = (V, E) and H = (W, F) displayed in the following figure are isomorphic.
15. Prove that “a simple graph is connected if and only if it has a spanning tree”.
15. Prove that a tree with n-vertices has n-1 edges.
15. Prove that an undirected graph is a tree if there is a unique simple path between any two of its vertices.
15. Define rooted tree. Show that a full m-ary tree with i internal vertices contains n = mi + 1 vertices.
15. Define isomorphism. Given an example to show that the graphs are not isomorphic.
15. Find a spanning tree of the simple graph in the following graph, if it exists.
Can there be more possibilities?
15. Show that the maximum number of vertices in a binary tree of height n is 2n+1 − 1.
OR
Draw all possible unordered trees on the set {a, b, c}.
17. What is shortest path problem? Find the length of a shortest path between a and z in the given weighted
graph.
18. Find the maximum flow in the network shown in the figure.
18. Discuss the algorithm for constructing Euler circuit with suitable example.
18. Find a maximum flow in the network shown in figure
19. Describe Dijkstra’s algorithm for finding the shortest path in a weighted graph between two vertices with suitable example.
19. A phrase structure grammar g is defined to be a 4-tuple (V, S, v0 |→ ), where V=(vo, w, a, b, c}, S={a, b, c}, vo |→ 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.
19. State and prove the Max-flow and Min-cut theorem.
OR
Find a maximum flow for the network in the figure below.
19. Explain the concept of network flows and max-flow min-cut theorem with suitable examples.
OR
Define Euler circuit and Euler path with suitable examples. Give the multi-graph model of the two of Koenigsberg state a necessary and sufficient condition for Euler circuit in connection to your definitions and models.
19. Define an Euler circuit and Euler path in an undirected graph. How can it be determined whether an undirected graph has an Euler circuit and an Euler path? Explain with suitable example.
19. An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.
19. Discuss Kruskal’s algorithm for constructing a minimum spanning tree. Use this algorithm to find minimum spanning tree in the graph given below.
19. What do you mean by spanning tree? Find a spanning tree of the simple graph G shown in figure.
A graph is connected if and only if it has a spanning tree.
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.
19. Prove that a symmetric connected relation has a undirected spanning tree.
OR
Give a simple condition on the weights of a graph that will guarantee that there is a unique maximal spanning tree for the graph.
19. Explain the concept of network flows and max-flow min-cut theorem with suitable examples.
20. Find all S-D cuts in the following transport network. What is the value of a maximal flow?
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.
20. Use Fleury’s algorithm to construct an Euler circuit for the following graph.
OR
Explain the concept of network flows and max-flow min- cut with suitable examples.
20. Explain the concept of network flows and max-flow min-cut theorem with suitable examples.
20. State and prove Max-Flow Min-Cut theorem.
20. Find a maximal flow for the network shown in the figure below:
20. Define maximal flow and minimal cut and state and prove min-cut max-flow theorem.
OR
Find a maximal flow for the network shown in the figure below:
20. Discuss the Algorithm of Dijkstra for finding the shortest path in a weighted graph between two vertices with suitable example. Moreover, explain the travelling salesman problem and the efficiency of algorithm for solving this problem.
20. Define Hamiltonian paths and circuits with suitable examples for the existence and nonexistence. Show that has a Hamilton circuit whenever .
OR
Write the shortest path algorithm of Dijkstra for finding the shortest path between two vertices. What is the length of shortest path between a and z in the weighted graph in the following figure?
Apply the stated algorithm for finding the solution.
20. Define Euler and Hamiltonian circuits and paths with examples illustrating the existence and nonexistence of them.
OR
Discuss the shortest path algorithm of Dijkstra for finding the shortest path between two vertices. Use this algorithm to find the length of the shortest path between a and z in the following weighted graph?
Give the idea of travelling salesman problem and the difficulties of solving it.
5. Define the terms a language over a vocabulary and the phrase – structure grammar.
6. What is context free grammar?
5. Define the terms a language over a regular grammer and regular expression.
6. Define the terms a language over a vocabulary and the phrase-structure grammar.
7. Differentiate between DFA and NFA.
6. What is phrase-structure grammar?
6. Define the terms a language over a regular grammar and a regular expression.
6. Discuss the types of phrase structure grammars and their relations.
6. Let G be the grammar with vocabulary V = {S, A, a, b}, t = {a, b}, starting symbol S and production P = {S→ aA, S→ b, A→ aa}. What is L(G), the language of this grammar ?
7. What is regular expression?
7. Explain the state transition function of the finite state machine with a suitable table.
7. Give formal definition of regular expressions over a set I.
7. Distinguish between deterministic and nondeterministic finite state automaton.
7. Determine the kleen closures of the sets A = {0}, B = {0, 1}, C = {11}.
8. Explain the static transition function of the finite state machine with a suitable table.
8. Let A = {0, 1}. Show that the following expressions are all regular expressions over A
a) 0* (0v1)* b) 00* (0v1)* 1.
9. Define regular expression over a non empty set A.
9. Define regular expression over a non-empty set A.
9. What are the strings in the regular sets specified by the regular expression (10)*.
9. What is a phrase-structure grammar?
10. Explain non-deterministic finite state automata.
10. What are the strings in the regular sets specified by the regular expression 10*.
10. Let G be the grammar with vocabulary V = {S, 0, 1}, set of terminals T = {0, 1}, starting symbol S, and productions P = {S → 11S, S → 0}. What is L (G), the language of this grammar?
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, ...}
13. Let G be the grammar with vocabulary V= {S, A, a, b}, set of terminals T ={a,b}, starting symbol S, and productions P ={S→aA, S→b, A→aa}. What is L(G), the language of this grammar?
12. Let A = {p, q, r}. Give the regular set corresponding to the regular expression given:
a) (p v q ) ┌ q* b) p( q q )* r.
12. Let A = {p, q, r} . Give the regular set corresponding to the regular expression give:
(a) (pvq)rq* (b) p(q q) r.
13. Let G be the grammar with vocabulary V = {S, 0, 1}, set of terminals T= {0, 1}; starting symbol S, and productions P= {S→11s, S→0}. Determine the language L(G) of this grammar.
13. Define finite-state with output with suitable examples.
OR
Define deterministic finite state automata. When are two finite state automata equivalent? Give an
example.
13. How do you distinguish deterministic and nondeterministic finite-state automaton? Give suitable examples.
13. Explain the finite-state with output with suitable examples.
OR
Explain the deterministic finite state automata. When are two finite state automata equivalent?Give an example.
13. Define deterministic finite state automata. Construct a DFA whose language is the set of strings that ends with 111 and contains odd number of 1’s.
14. Define finite – state machines with output.
15. Construct a nondeterministic finite-state automaton that recognizes the regular set 1* ∪ 01.
15. Let G be the grammar with vocabulary V = {S, 0, 1}, set of terminals T = {0, 1}, starting symbol S, and production P ={ S→ 11S,S→0}. What is the L(G) of this grammar?
16. Define deterministic finite state automata. When are two finite state automata equivalent? Explain it.
16. Construct the transition table of the finite – state machine whose diagraph is shown?
18. Discuss finite state machine with output with suitable example. What are the strings in the regular set specified by the regular expression 01*0?
17. Construct the state transition table of the finite state machine whose diagram is shown:
17. Let G = ( V, S, v0, |→), where V = { v0, x, y, z}, S = {x, y, z } and
|→ : v0 |→ xv0
v0 |→ yv0
v0 |→ z
What is L(G), the language of this grammar?
18. Explain non-homogeneous finite automata and language of NFA with suitable example.
18. What do you mean by phase-structure grammar? Let C1 be the grammar with vocabulary V = {S, 0, 1}; set of terminals T= {0, 1}; starting symbol S, and productions P= {S→11s, S→0}. Determine the language L(G) of this grammar.
18. Discuss finite state machine without output with suitable example. What are the strings in the regular set specified by the regular expression 0* 1*?
18. Let G be the grammar with vocabulary V = {S, 0,1} , set of terminals T = {0,1} , starting symbol S, and
productions P = {S → 11S, S → 0}. What is L(G), the language of this grammar?