1. Complement of regular sets are _________
a) Regular
b) CFG
c) CSG
d) RE
View Answer
Answer:a
Explanation: Regular sets are closed under complement operation.
Explanation: Regular sets are closed under complement operation.
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned
View Answer
Answer : d
Explaination : None.
Explaination : None.
a) n
b) n1/2
c) n2
d) 2n
View Answer
Answer: a
Explanation: The conversion DFA to NFA is simple, and takes O(n) time on an n-state DFA.
Explanation: The conversion DFA to NFA is simple, and takes O(n) time on an n-state DFA.
General syntax of sed: /pattern/action
a) / are used as delimiters
b) pattern refers to a regular expression
c) pattern refers to the string to be matched
d) action refers to the command
View Answer
Answer: c
Explanation: In the general syntax of sed, pattern is the regular expression and action refers to the command given (p: prints the line, d: deletes the line, etc).
Explanation: In the general syntax of sed, pattern is the regular expression and action refers to the command given (p: prints the line, d: deletes the line, etc).
a) a
b) a+F
c) a+?
d) wrong expression
View Answer
Answer : c
Explanation : Zero or one time repetition of previous character .
Explanation : Zero or one time repetition of previous character .
a) Homomorphism
b) Inverse Homomorphism
c) Reversal
d) All of the mentioned
View Answer
Answer: d
Explanation: Homomorphism on an aphabet is a function that gives a string for each symbol in that alphabet. Example: h(0)=ab, etc.
Explanation: Homomorphism on an aphabet is a function that gives a string for each symbol in that alphabet. Example: h(0)=ab, etc.
a) NFA to DFA
b) Lazy DFA algorithm
c) Backtracking
d) None of the mentioned
View Answer
Answer: d
Explanation: There are at least three algorithms which decides for us, whether and how a regexp matches a string which included the transformation of Non deterministic automaton to deterministic finite automaton, The lazy DFA algorithm where one simulates the NFA directly, building each DFA on demand and then discarding it at the next step and the process of backtracking whose running time is exponential.
Explanation: There are at least three algorithms which decides for us, whether and how a regexp matches a string which included the transformation of Non deterministic automaton to deterministic finite automaton, The lazy DFA algorithm where one simulates the NFA directly, building each DFA on demand and then discarding it at the next step and the process of backtracking whose running time is exponential.
a) Subset Construction method
b) Warshalls Algorithm
c) Ardens theorem
d) None of the mentioned
View Answer
Answer: a
Explanation: Powerset or subset construction method is a standard method for converting a non deterministic finite automata into DFA which recognizes the same formal language.
Explanation: Powerset or subset construction method is a standard method for converting a non deterministic finite automata into DFA which recognizes the same formal language.
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
View Answer
Answer: a
Explanation: Regular grammar is a subset of context free grammar and thus all regular grammars are context free.
Explanation: Regular grammar is a subset of context free grammar and thus all regular grammars are context free.
L={ambmcm| m>=1}
a) Context free language
b) Regular language
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: d
Explanation: The given language is neither accepted by a finite automata or a push down automata. Thus, it is neither a context free language nor a regular language.
Explanation: The given language is neither accepted by a finite automata or a push down automata. Thus, it is neither a context free language nor a regular language.
Statement: Every right-linear grammar generates a regular language.
a) True
b) False
View Answer
Answer: a
Explanation: A CFG is said to right linear if each production body has at most one variable, and that variable is at the right end. That is, all productions of a right linear grammar are of the form A->wB or A->w, where A and B are variables while w is some terminal.
Explanation: A CFG is said to right linear if each production body has at most one variable, and that variable is at the right end. That is, all productions of a right linear grammar are of the form A->wB or A->w, where A and B are variables while w is some terminal.
a) Root with no children is called a leaf
b) A node can have three children
c) Root has no parent
d) Trees are collection of nodes, with a parent child relationship
View Answer
Answer: a
Explanation: A node has atmost one parent, drawn above the node, and zero or more children drawn below. Lines connect parents to children. There is one node, one root, that has no parent; this node appears to be at the top of the tree. Nodes with no children are called leaves. Nodes that are not leaves are called interior nodes.
Explanation: A node has atmost one parent, drawn above the node, and zero or more children drawn below. Lines connect parents to children. There is one node, one root, that has no parent; this node appears to be at the top of the tree. Nodes with no children are called leaves. Nodes that are not leaves are called interior nodes.
a) G has no useless symbols
b) G has no unit productions
c) G has no epsilon productions
d) None of the mentioned
View Answer
Answer: d
Explanation: G, a CFG is said to be in Chomsky normal form if all its productions are in one of the following form:
A->BC or A->a
Explanation: G, a CFG is said to be in Chomsky normal form if all its productions are in one of the following form:
A->BC or A->a
a) LALR parser
b) LL parser
c) Recursive Accent parser
d) None of the mentioned
View Answer
Answer: b
Explanation: Bottom up parsing is done by shift reduce parsers like LALR parsers, Operator precedence parsers, simple precedence parsers, etc.
Explanation: Bottom up parsing is done by shift reduce parsers like LALR parsers, Operator precedence parsers, simple precedence parsers, etc.
a) LALR parsing
b) LL parsing
c) GLR parsing
d) None of the mentioned
View Answer
Answer: a
Explanation: LALR parser generator is software tool that reads a BNF grammar and creates a LALR parser which is capable of parsing files written in programming language identified by BNF grammar.
Explanation: LALR parser generator is software tool that reads a BNF grammar and creates a LALR parser which is capable of parsing files written in programming language identified by BNF grammar.
