FLAT Long Questions



1.      What is computation? What are the different models of Computation? Explain
2.      What are the different classes of automata? How they are classified? Expalin in details
3.      Give the formal definition of FSM? What are the examples of FSM?
4.      What is state diagram and state transition table. Explain with an example?
5.      What are the components of FSM? Explain.
6.      Write a short note on classification of automata
7.      Construct a finite automata with transition for the regular expression r=01*+10
8.      Define cellular and geographic automata.
9.      What are the different operations on strings? Explain with examples?
10.  What are the different types of languages in automata theory? Clearly give the rules for each of these languages and the relationship among these languages
11.  Consider a language L*, where L={ab, cd} with Σ={a, b, c, d}.
12.  Write all words in L* that have six or less letters/symbols
13.  What is the shortest string in Σ* that is not in the Language L*?
14.  What is push down automata? Show how CFL is accepted by push down automata.
15.  Differentiate NFA with DFA
16.  Describe on detail about recursive enumerable language
17.  Write regular expression for the language over{0, 1}: the set of all strings that contain 1011.
18.  Write a short notes on i) symbols ii) Alphabets and iii) Strings.
19.  Write a short note on PDA with an example.
20.  Write the regular expression for the language over {0, 1}: the set of all strings that contain 100.
21.  Construct a DFA accepting the language L={ w: |w| mod 8 ≠ 0} on Σ ={a, b}
22.  Obtain a DFA to accept strings of a’s and b’s such that, each block of 5 consecutive symbols has at least two a’s.
23.  Construct a DFA accepting the language: {W ϵ{a, b} *: W has both ab and ba as substrings}
24.  Design a ϵ-NFA for the regular expression a*bc/ab*/c*
25.  Construct a DFA accepting the language: {W ϵ{a, b} *: W has neither aa nor bb as substring}
26.  Design a ϵ-NFA for the regular expression a*/b*/c*
27.  Design ϵ-closure of a state? Give an example
28.  Design a DFA to accept odd number of a’s and even number of b’s, where Σ={a, b}. Show the acceptance of a string with an example
29.  Design a ϵ-NFA for the regular expression a*b/cb*/ac*b
30.  What is Arden’s theorem. Explain
31.  Convert the following DFA to RE
0
1
p
p
q
q
q
r
r
r
r
32.  Check the following two DFA are equal or not
0
1
q1
q1
q2
q2
q3
q1
q3
q2
q3

0
1
q4
q4
q4
q5
q6
q4
q6
q4
q6
q7
q6
q4
33.  List out the properties of Regular sets and regular languages
34.  Minimize the following DFA, where state ‘0’ is the start and 3, 5, 6 & 7 are the final states
a
b
0
1
2
1
4
5
2
3
-
3
-
-
4
4
2
5
6
-
6
7
-
7
7
-

35.  What is Chomsky’s Hierarchy? Explain
36.  What is Unit Production? What is the procedure to remove the unit productions in CFG.
37.  Convert the following grammar to CNF SàbA|aB, AàbAA|aS|a, BàaBB|bSbb
38.  Design a total turing machine to accept the language: L2 = {wϵ {a, b, c}*| #a(w) ≤ #b(w)≤ #c(w)} (note: # means number)
39.  Explain about P and NP classes of Languages.
40.  What is use of simplification of CFG? What is the procedure to simplify the CFG? Explain
41.  Simplify the following grammar. SàaAa, AàbBB/D, Bàab/ϵ, CàaB
42.  Give the formal definition of TM? What are the components of TM? What is id of TM?
43.  Design a Turing Machine for the { L=WWR/Wϵ(0+1)*}
44.  Define Chomsky Normal form and Greibach Normal Form? what is the difference between these two normal forms.
45.  Convert the following CFG into GNF A1àA2A3, A2àA3A1/b, A3àA1A2/a
46.  Given the formal definition of TM? What are the different types of TMs?
47.  Design a Turing Machine for the {L=WCWR/Wϵ(0+1)*}
48.  What is normalization of CFG? What is the use of Normalization? What are the different normal forms? Explain
49.  Convert the following CFG into GNF.
50.  SàAA/0, AàSS/1
51.  Design Turing Machine to compute the function n! (Factorial of a number)
52.  Explain about undecidable problem

Comments

Post a Comment

Popular posts from this blog

Tree pruning useful in decision tree induction

Why is tree pruning useful in decision tree induction? What is a drawback of using a separate set of tuples to evaluate pruning? The decision tree built may overfit the training data. There could be too many branches, some of which may reflect anomalies in the training data due to noise or outliers. Tree pruning addresses this issue of overfitting the data by removing the least reliable branches (using statistical measures). This generally results in a more compact and reliable decision tree that is faster and more accurate in its classification of data. The drawback of using a separate set of tuples to evaluate pruning is that it may not be representative of the training tuples used to create the original decision tree. If the separate set of tuples are skewed, then using them to evaluate the pruned tree would not be a good indicator of the pruned tree’s classification accuracy. Furthermore, using a separate set of tuples to evaluate pruning means there are less tuples to use for ...
Read more

Machine Learning Syllabus

MACHINE LEARNING UNIT -I: The ingredients of machine learning, Tasks: the problems that can be solved with machine learning, Models: the output of machine learning, Features, the workhorses of machine learning. Binary classification and related tasks: Classification, Scoring and ranking, Class probability estimation UNIT-II: Beyond binary classification:  Handling more than two classes, Regression, Unsupervised and descriptive learning. Concept learning : The hypothesis space, Paths through the hypothesis space, Beyond conjunctive concepts UNIT- III: Tree models: Decision trees, Ranking and probability estimation trees, Tree learning as variance reduction. Rule models: Learning ordered rule lists, Learning unordered rule sets, Descriptive rule learning, First-order rule learning UNIT-IV: Linear models: The least-squares method, The perceptron: a heuristic learning algorithm for linear classifiers, Support vector machines, obtaining probabilities from linear cla...
Read more