CS402 Final Term Quiz by Mueen

➢ This File is based on the MCQS of 2 nd Quiz on · Dated 24th August 2021. · ➢ This file will also help in the final. All options · are marked with extreme care, but still · human error is possible. · ➢ First 60 MCQs are from the 2nd quiz, and · remaining (Al-Junaid File) is added for · further accuracy and for final term. · Regards Mueen Hasan (MCS 1 st)

1. In new format of an FA (discussed in lecture 37):……state is like a final state of an FA START

REJECT READ

2. In conversion form of PDA there is no……………. state

PUSH ACCEPT

READ

3. Given a PDA that accepts the language L

There does not exist any CFG that generates exactly L that PDA will also accept Language L' (complement of L)

4. In a CFG the non-terminal that occurs first from the left in the working string. is said to be Least Significant nonterminal Left most nonterminal (Handouts Page # 103) Most Significant nonterminal Left most derivate

5. The structure given below is called

S -> aAlbB

A -> aSla

B -> bSIb

RE PDA CFG (It is form of CFG) TG

6. An FA has N states then it must accept the word of length

2N N N-1 N-1

7. To examine whether a certain FA accepts any words. it is required to seek the paths……..state. from initial to final (Handouts Page # 81) from initial-to-initial back from final to initial from final to back final
8. In nondeterministic PDA. a string is supposed to be accepted if there exists at least one path traced by the string. leading to………..state. START REJECT READ

9. If a CFG has a null production, then it is

Called Null CFG Not possible to construct another CFG without null production accepting the same language with the exception of the word Called Chmosky Normal Form (CNF) Possible to construct another CFG without null production accepting the same language with the exception of the word

10. There is at least one production in CFG that has one……………. on its left side. Non terminal (Handouts Page # 87) Null production Terminal Unit production
11. In large FA with thousands of states and millions of directed edges, without an effective
12. By removing null and unit productions__________. CNF can be converted into FA CNF can be converted into CFG CFG can be converted into CNF (Handouts Page # 102) CNF can be converted into Turing machine

13. A………is the one for which every input string has a unique path through the machine

deterministic PDA Input Tape nondeterministic PDA PUSHDOWN store

14. PDA stands for

Push Down Automaton (Handouts Page # 112) Pop and Drop Automaton Push and Drop Automaton Push Deterministic Automaton

15. A PDA is called nondeterministic PDA if

there are more than one POP states there are more than one PUSH states there are more than one outgoing edges at READ or POP states with one label every READ state is followed by a HERE state.