COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Complement
|
|
|
Union
|
|
|
Disjoint
|
|
|
Connected
|
Detailed explanation-1: -Explanation: Two sets are called disjoint if they have no elements in common i.e. RÇT=Æ. 2. Which among the following is not a part of the Context free grammar tuple?
Detailed explanation-2: -Acceptance by Empty Stack: On reading the input string from the initial configuration for some PDA, the stack of PDA gets empty. Let P =(Q, ∑, , , q0, Z, F) be a PDA. The language acceptable by empty stack can be defined as: N(PDA) = w | (q0, w, Z) ⊢* (p, , ), q ∈ Q
Detailed explanation-3: -Which of the operations are eligible in PDA? Explanation: Push and pop are the operations we perform to operate a stack. A stack follows the LIFO principle, which states its rule as: Last In First Out.
Detailed explanation-4: -Which among the following cannot be accepted by a regular grammar? Explanation: There exists no finite automata to accept the given language i.e. 0n1n.
Detailed explanation-5: -The transition a Push down automaton makes is additionally dependent upon the: a) stack b) input tape c) terminals d) none of the mentioned Answer: a Explanation: A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.