New Microsoft Word Document.pdf

Choose the Number of states require to accept string ends with 101 3 4 2 cann't be determined Given the language L = {ab, aa, baa}, predict which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa 1, 2 and 3 2, 3 and 4 1, 2 and 4 1, 3 and 4 Determine wheth...

Choose the Number of states require to accept string ends with 101 3 4 2 cann't be determined Given the language L = {ab, aa, baa}, predict which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa 1, 2 and 3 2, 3 and 4 1, 2 and 4 1, 3 and 4 Determine whether a DFA recognize a palindrome number? Yes No Yes, with input alphabet as a* cann\'t be determined Interprit how many languages are over the alphabet R? countable infinite countable finite uncountable finite uncountable infinite The transition function in a finite automaton is typically represented as: δ: Q × Σ → Q δ: Q × Σ → P(Q) both a and b none Choose which of the following options is correct? Statement 1: Initial State of NFA is Initial State of DFA. Statement 2: The final state of DFA will be every combination of final state of NFA. Statement 1 is true and Statement 2 is true Statement 1 is true and Statement 2 is false Statement 1 can be true and Statement 2 is true Statement 1 is false and Statement 2 is also false Choose A regular language over an alphabet ∑ is one that cannot be observed from the basic languages using which of the operation Union Concatenation Kleene* All of the mentioned Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be its states; Statement 3: The edges or arcs can be used for transitions Choose the option that make the correct combination? Statement 1 is false but Statement 2 and 3 are correct Statement 1 and 2 are correct while 3 is wrong None of the mentioned statements are correct All of the mentioned are correct Choose the number of final states require to accept Φ in minimal finite automata. 1 2 3 None of the mentioned Determine A DFA cannot be represented in which of the following format MCQ (Text) Transition graph Transition Table C code None of the mentioned The minimum number of states required to recognize an octal number divisible by 3 can be computed as 1 3 5 7 Determine the one from the following is not an example of finite state machine system? Control Mechanism of an elevator Combinational Locks Traffic Lights Digital Watches State the purpose of the transition function in a finite automaton? To specify the start state of the automaton. To define the alphabet of the automaton. To map a state and an input symbol to a set of states. To determine the set of accept states. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________. determine the correct answer. Compiler Interpreter Loader and Linkers None of the mentioned Extended transition function is interpreted as. Q * Σ* -> Q Q * Σ -> Q Q* * Σ* -> Σ Q * Σ -> Σ Given: ∑= {a, b} L= {xϵ∑*|x is a string combination} ∑4 computes to which one among the following? {aa, ab, ba, bb} {aaaa, abab, ε, abaa, aabb} {aaa, aab, aba, bbb} All of the mentioned The non- Kleene Star operation develops the following string of finite length over set A = {0,1} | where string s contains even number of 0 and 1 10011010101 1111001100 ε,0011,11001100 ε,0011,11001100 The password to the admins account=”administrator”. The total number of states required to prepare a password-pass system using DFA would be __________ 14 states 13 states 12 states A password pass system cannot be created using DFA Let ∑= {a, b, …. z} and A = {Hello, World}, B= {Input, Output}, then (A*∩B) U (B*∩A) can be determined as: {Hello, World, Input, Output, ε} {Hello, World, ε} {Input, Output, ε} {} The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is examined as _________ 7 6 8 5 Judge that which one of the following is correct proposition? Statement 1: Non-determinism is a generalization of Determinism. Statement 2: Every DFA is automatically an NFA Statement 1 is correct because Statement 2 is correct Statement 2 is correct because Statement 1 is correct Statement 2 is false and Statement 1 is false Statement 1 is false because Statement 2 is false Determine which of the following option is correct? NFA is slower to process and its representation uses more memory than DFA DFA is faster to process and its representation uses less memory than NFA NFA is slower to process and its representation uses less memory than DFA DFA is slower to process and its representation uses less memory than NFA Examine which of the following the given language belongs to? L={ambmcm|m>=1} Context free language Regular language Both (a) and (b) None of the above If A->aA| a| b, determine the number of steps to form aab: 2 3 4 5 Judge which of the following pair of regular expression that are not equivalent? 1(01)* and (10)*1 x(xx)* and (xx)*x (ab)* and a*b* x+ and x*x+ Examine which of the following is true? (01)*0 = 0(10)* (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)* (0+1)*01(0+1)*+1*0* = (0+1)* All of the mentioned Consider the following two statements: S1: { 02n |n >= l} is a regular language S2: {0m 0n 0(m+n) | m >= 1 and n >= 2} is a regular language Determine which of the following statements is correct? Only S1 is correct Only S2 is correct Both S1 and S2 are correct None of S1 and S2 is correct Regular expressions are illustrated to be closed under Union Intersection Kleen star All of the mentioned Compute the minimum number of productions required to produce a language consisting of palindrome strings over input alphabets {a, b} is 3 7 5 6 Let the class of language accepted by finite state machine be L1 and the class of languages recognized by regular expressions be L2 then L1 L1>=L2 L1 U L2 = L* L1=L2 Languages of a automata is defined as If it is accepted by automata If it halts If automata touch final state in its life time All language are language of automata The basic limitation of finite automata is observed as It can’t remember arbitrary large amount of information It sometimes recognizes grammar that are not regular. It sometimes fails to recognize regular grammar. All of the mentioned Finite automata describe the requirement of minimum _______ number of stacks. 1 0 2 None of the mentioned Define when are 2 finite machines equivalent? Same number of transitions Same number of states Same number of states as well as transitions Both are final states If S->....->xAy->....->w, then A is described as _____________ Reachable Generating Both Reachable and Generating None of the mentioned The complement of a language will only be defined when and only when the __________ over the language is defined. String Word Alphabet Grammar Select which of the following is an application of Finite Automaton? Compiler Design Grammar Parsers Text Search All of the mentioned An automaton that presents output based on previous state or current input is stated as: Acceptor Classifier Transducer None of the mentioned. Select the kind of expressions do we used for pattern matching? Regular Expression Rational Expression Regular & Rational Expression None of the mentioned Select from the following, Regular grammar is accepted by Turing machine Finite automata Linear bound automata Push down automata The entity which generate Language is explained as: Automata Tokens Grammar Data Recall which of the following is not a part of 5-tuple finite automata? Input alphabet Transition function Initial state Output alphabet A language is defined to be regular if and only if accepted by DFA accepted by PDA accepted by LBA accepted by Turing machine Regular Expression define precisely the ________ of Regular Language. Class Power Set Super Set None of the mentioned Observe which of the expression is appropriate? For production p: a->b where a∈V and b∈_________ V S (V+∑)* V+ ∑ Precedence of regular expression in decreasing order is ordered as *,.,+.,*,+.,+,* +,a,* Identify that Arden’s theorem is true for More than one initial states Null transitions Non-null transitions None of these Choose which of the following is not a notion of Context free grammars Recursive Inference Derivations Sentential forms All of the mentioned Recognize the options which support the given statement? Statement: A regular expression could be a fixed word or describe something like more general. This flexibility makes Regular expression invaluable This flexibility makes the Regular expression unvaluable This flexibility makes Regular expression invaluable and unvaluable None of the mentioned Estimate which of the following not an example Bounded Information? fan switch outputs {on, off} electricity meter reading colour of the traffic light at the moment None of the mentioned Select which of the following is true? Every subset of a regular set is regular Every finite subset of non-regular set is regular The union of two non-regular set is not regular Infinite union of finite set is regular In a deterministic finite automaton (DFA), how many transitions does each state have for a given input symbol? 0 1 multiple none Given grammar G: (1) S->AS (2) S->AAS (3) A->SA (4) A->aa Select the following productions which denies the format of Chomsky Normal Form? 2, 4 1, 3 1, 2, 3, 4 2, 3, 4 Select which among the following is not notated as infinite language? Palindrome Reverse Factorial L={ab}* δ explains the best: transition function translation function equivalence Kleene operation is performed on the set In order to recognize a regular expression, the first step to create the transition diagram is: Create the NFA using Null moves Null moves are not acceptable, thus should not be used Predict the number of states to be used in order to construct the Regular expression None of the mentioned (0+ε) (1+ε) recognizes {0, 1, 01, ε} {0, 1, ε} {0, 1, 01 ,11, 00, 10, ε} {0, 1} Explain which of the following is not a regular expression? [(a+b)*(aa+bb)]* [(0+1)(0b+a1)*(a+b)]* (01+11+10)* (1+2+0)*(1+2)* Production Rule: aAb->agb enumerate which of the following category? Regular Language Context free Language Context Sensitive Language Recursively Enumerable Language Recognize which of the following statement is correct? All Regular grammar are context free but not vice versa All context free grammar are regular grammar but not vice versa Regular grammar and context free grammar are the same entity None of the mentioned Determine how many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*? 7 10 12 11 Consider following regular expression i) (a/b)* ii) (a*/b*)* iii) ((ϵ/a)b*)* Which of the following statements is manipulated as correct i,ii are equal and ii,iii are not i,ii are equal and i,iii are not ii,iii are equal and i,ii are not all are equal The following regular expression: ε+1*(011) *(1*(011) *) * is computed as (1+011) * (1*(011) *) (1+(011) *) * (1011) * Given grammar G: S->aS| AB A-> epsilon B-> epsilon D-> b Discover the grammar, removing all the epsilon productions: S->aS| AB| A| B, D-> b S->aS| AB| A| B| a, D-> b S->aS| AB| A| B None of the mentioned Choose the correct option: Statement 1: Recursive Inference, using productions from head to body. Statement 2: Derivations, using productions from body to head. Statement 1 is true and Statement 2 is true Statement 1 and Statement 2 both are false Statement 1 is true and Statement 2 is false Statement 1 is false and Statement 2 is true Determine which of the following statements are correct for a concept called inherent ambiguity in CFL? Every CFG for L is ambiguous Every CFG for L is unambiguous Every CFG is also regular None of the mentioned What does the transition function return for a given state and input symbol in a nondeterministic finite automaton (NFA)? A single state A set of states An output symbol The next state Determine which of the following statement is false in context of tree terminology? Root with no children is called a leaf A node can have three children Root has no parent Trees are collection of nodes, with a parent child relationship Choose in which order are the children of any node ordered? From the left From the right Arbitrarily None of the mentioned For the expression E*(E) where * and brackets are the operation, discover the total number of nodes in the respective parse tree are: 6 7 5 2 If w belongs to L(G), for some CFG, then w has a parse tree, which tell us the ________ structure of w. Determine the correct option. semantic syntactic lexical all of the mentioned Choose the correct option: Statement: Unambiguity is the ideal structure of a language. 1 partially true Can’t be said Choose which of the following are always unambiguous? Deterministic Context free grammars Non-Deterministic Regular grammars Context sensitive grammar None of the mentioned Discover among the following is the correct grammar for the given language? L={x∈{0,1}*|number of zeroes in x¹number of one’s in x} S-> 0|SS|1SS|SS1|S1S S-> 1|0S|0SS|SS0|S0S S-> 0|0S|1SS|SS1|S1S None of the mentioned AB →AbBc is a type 1 production. Choose here the left and right contexts are A and ε respectively ε and B respectively Ab and c respectively Both are null Choose which of the following is not a notion of Context free grammars Recursive Inference Derivations Sentential forms All of the mentioned Judge from the following is/are the suitable approaches for inferencing? Recursive Inference Derivations Recursive Inference and Derivations None of the mentioned Discover among the following is the correct option for the given grammar? G->X111|G1,X- >X0|00MCQ (Text) {0a1b|a=2, b=3} {0a1b|a=1, b=5} {0a1b|a=b} More than one of the mentioned is correct Choose the correct option: Statement 1: Recursive Inference, using productions from head to body. Statement 2: Derivations, using productions from body to head. Statement 1 is true and Statement 2 is true Statement 1 and Statement 2, both are false Statement 1 is true and Statement 2 is false Statement 2 is true and Statement 1 is true Judge which of the following statements are correct for a concept called inherent ambiguity in CFL? Every CFG for L is ambiguous Every CFG for L is unambiguous Every CFG is also regular None of the mentioned The minimum number of 1’s to be used in a regular expression of the given language: R(x): The language of all strings containing exactly 2 zeroes. Choose the correct answer. 2 3 0 1 The given regular language explains which of the given regular language ∈+1+(1+0)*0+(0+1)*11 The language of all strings that end with 11 or 00 The language of all strings that end with 0 or 1 The language of all strings which does not end with 01 None of the mentioned Statement: If we take the union of two identical expression, we can replace them by one copy of the expression. Which of the following employ’s a correct option for the given statement? Absorption Law Idempotent Law Closure Law Commutative Law Statement: Left most derivations are lengthy as compared to Right most derivations. Choose the correct option: correct statement incorrect statement may or may not be correct depends on the language of the grammar A->aAa|bAb|a|b|∈ Choose among the following is the correct option for the given production? Left most derivation Right most derivation Recursive Inference None of the mentioned Determine the technique can be used to prove that a language is non-regular? Ardens theorem Pumping Lemma Ogden’s Lemma None of the mentioned Judge from the following the language that are non-regular? The set of strings in {a,b}* with an even number of b’s The set of strings in {a, b, c}* where there is no c anywhere to the left of a The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3 None of the mentioned A symbol X is called to be useful if and only if it explains to be: generating reachable both generating and reachable none of the mentioned Choose from the following which is false for a grammar G in Chomsky Normal Form: G has no useless symbols G has no unit productions G has no epsilon productions None of the mentioned Determine which of the following are distinct to parse trees? abstract parse trees sentence diagrams both abstract parse trees and sentence diagrams none of the mentioned Explain which of the following allows stacked values to be sub-stacks rather than just finite symbols? Push Down Automaton Turing Machine Nested Stack Automaton None of the mentioned Discover the operations are eligible in PDA? Push Delete Insert Add Identify the situation when a string is accepted by a PDA. Stack is not empty Acceptance state All of the mentioned None of the mentioned The move of a PDA is discover on the basis of: Present state Input Symbol Present state and Input Symbol None of the mentioned In non-deterministic PDA, there are more than one out going edges from the following selected states? READ or POP START or READ POP or REJECT PUSH or POP identify which of the following statement is false? For non-deterministic PDA, equivalence is undecidable For deterministic PDA, equivalence is decidable For deterministic PDA, equivalence is undecidable None of the mentioned Discover the trueness for the given statement? Statement: If there are strings R and T in a language L so that R is prefix of T and R is not equivalent to T. No DPDA can accept L by empty stack DPDA can accept L by an empty stack L is regular None of the mentioned Let Input Alphabets={0,1}* and the grammar G be: S->epsilon S->SS S->0S1|1S0 Discover which of the following is true for the given statement Language of all and only Balanced strings It contains equal number of 0\'s and 1\'s Ambiguous Grammar All of the mentioned Identify the highest type number which can be applied to the following grammars: S→ As |ab Type 0 Type 1 Type 2 Type 3 If the PDA does not stop on an accepting state and the stack is not empty, the string is distinguished as- rejected goes into loop forever All of the mentioned None of the mentioned Identify which of the following assertion is false? If L is a language accepted by PDA1 by final state, there exist a PDA2 that accepts L by empty stack i.e. L=L(PDA1)=L(PDA2) If L is a CFL then there exists a push down automata P accepting CF; by empty stack i.e. L=M(P) Let L is a language accepted by PDA1 then there exist a CFG X such that L(X)=M(P) All of the mentioned Let ∑={0,1}* and the grammar G be: S->ε S->SS S->0S1|1S0 discover which of the following is true for the given Language of all and only Balanced strings It contains equal number of 0’s and 1’s Ambiguous Grammar All of the mentioned The transition a Push down automaton makes is additionally dependent upon the___. State the correct option. stack input tape terminals none of the mentioned |-* is the __________ Explain as a closure of |- symmetric and reflexive transitive and reflexive symmetric and transitive none of the mentioned With reference of a DPDA, Explain which among the following do we perform from the start state with an empty stack? process the whole string end in final state end with an empty stack all of the mentioned A DPDA is Explain as a PDA in which: No state p has two outgoing transitions More than one state can have two or more outgoing transitions Atleast one state has more than one transitions None of the mentioned Finite-state acceptors for the nested words can be defined as: nested word automata push down automata ndfa none of the mentioned A language accepted by Deterministic Push down automata is estimated to be closed under which of the following? Complement Union All of the mentioned none of the mentioned Select which of the following are the actions that operates on stack top? Pushing Popping Replacing All of the mentioned A push down automata is explained to be _________ if it has atmost one transition around all configurations. Finite Non Reqular Non Deterministic Deterministic a→b Restriction: Length of b must be atleast as much length of a. Select which of the following is correct for the given assertion? Greibach Normal form Context Sensitive Language Chomsky Normal form Recursively Ennumerable language There exists a Context free grammar such that: X->aX Predict which among the following is correct with respect to the given assertion? Left Recursive Grammar Right Recursive Grammar Non Recursive Grammar None of the mentioned If the partial derivation tree associates the root as the starting variable, the form is known as: Chomsky Hierarchy Sentinal Form Root Form None of the mentioned Select a regular expression for a grammar which generates a language which states: L contains a set of strings starting wth an a and ending with a b, with something in the middle. a(a*Ub*)b a*(aUb)b* a(a*b*)b None of the mentioned Select among the following is incorrect with reference to a derivation tree? Every vertex has a label which is a terminal or a variable. The root has a label which can be a terminal. The label of the internal vertex is a variable. None of the mentioned Let G=(V, T, P, S) where a production can be written as: S->aAS|a, A->SbA|ba|SS Illustrate among which of the following string is produced by the grammar? aabbaab aabbaa baabab None of the mentioned Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar. Select which of the following options are correct with respect to the given statements? Statement 1 is true but statement 2 is false Statement 1 is false but statement 2 is true Both the statements are true Both the statements are false Select which among the following are non-essential while simplifying a grammar? Removal of useless symbols Removal of unit productions Removal of null production None of the mentioned The language L ={a^i2b^i|i>=0} is stated as: Recursive Deterministic CFL Regular Both A and B L->rLt|tLr|t|r The given grammar produces a language which is summarized as: All palindromes All even palindromes All odd palindromes Strings with same begin and end symbols A pushdown automaton can be explained as: (Q, ∑, G, q0, z0, A, d). What does the symbol z0 represents? an element of G initial stack symbol top stack alphabet all of the mentioned A turing machine defines a real machine abstract machine hypothetical machine more than one option is correct A turing machine operates over ________. Select the correct choice finite memory tape infinite memory tape depends on the algorithm none of the mentioned State which of the functions are not performed by the turing machine after reading a symbol? writes the symbol moves the tape one cell left/right proceeds with next instruction or halts none of the mentioned Select the problems that were not answered when the turing machine was invented? Does a machine exists that can determine whether any arbitrary machine on its tape is circular. Does a machine exists that can determine whether any arbitrary machine on its tape is ever prints a symbol Hilbert Entscheidungs problem None of the mentioned The ability for a system of instructions to simulate a Turing Machine is defined as _________ Turing Completeness Simulation Turing Halting None of the mentioned Turing machine can be recognized using the following tools: Transition graph Transition table Queue and Input tape All of the mentioned Select which of the following is false for an abstract machine? Turing machine theoretical model of computer assumes a discrete time paradigm all of the mentioned Fill in the blank with the most appropriate option. Statement: In theory of computation, abstract machines are often used in ___________ regarding computability or to analyze the complexity of an algorithm. thought experiments principle hypothesis all of the mentioned A turing machine that is able to simulate other turing machines is defined as: Nested Turing machines Universal Turing machine Counter machine None of the mentioned While applying Pumping lemma over a language, we observe a string w that belong to L and fragment it into _________ parts. 2 5 3 6 Let w= xyz and y refers to the middle portion and |y|>0. Define what do we call the process of repeating y 0 or more times before checking that they still belong to the language L or not? Generating Pumping Producing None of the mentioned There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n for some constant integer n. What can be the maximum length of the substring xy i.e. |xy|=n, there are strings u, v, w, x, y and z satisfying t=uvwxy. Let p be the number of variables in CNF form of the context free grammar. The value of n in terms of p is defined as 2p 2^p 2p+1 p^2 State among the following gives a positive result to the pumping lemma restrictions and requirements? {aibici|i>=0} {0i1i|i>=0} {ss|s∈{a,b}*} None of the mentioned Using pumping lemma, state which of the following cannot be proved as ‘not a CFL’? {aibici|i>=0} {ss|s∈{a,b}*} The set legal C programs None of the mentioned The class of recursively enumerable language is defined as: Turing Class Recursive Languages Universal Languages RE Define the pumping length of string of length x? x+1 x x-1 x^2 State which of the following does not obey pumping lemma for context free languages? Finite languages Context free languages Unrestricted languages None of the mentioned State which of the following is true for two stack turing machines? one read only input two storage tapes one read only input & two storage tapes None of the mentioned A deterministic turing machine is defined as: ambiguous turing machine unambiguous turing machine non-deterministic none of the mentioned Define which of the following is true about Turing’s a-machine? a stands for automatic left ended, right end-infinite finite number of tape symbols were allowed all of the mentioned Select the type of automata used for recognizing regular languages. Deterministic Finite Automata (DFA) Turing Machines Pushdown Automata Non-deterministic Turing Machines In terms of grammars, select what regular languages correspond to: Context-free grammars Regular expressions Chomsky grammars Unrestricted grammars Select the equivalence relationship between a Deterministic Finite Automaton (DFA) and a Regular Expression. DFA can recognize languages that Regular Expressions cannot Regular Expressions can recognize languages that DFA cannot They are equivalent, recognizing the same class of languages They have no relation to each other Select the type of automaton allowing multiple possible transitions for a given input symbol from a state. Deterministic Finite Automaton (DFA) Non-deterministic Finite Automaton (NFA) Turing Machine Pushdown Automaton Under the pumping lemma, select the property that regular languages satisfy: They can be divided into finite sets They can be split into multiple subsets They can be pumped or repeated to generate new strings in the language They cannot be recognized by any automaton Identify the main purpose of minimizing a finite automaton: To reduce the number of states while recognizing the same language To increase computational complexity To make the automaton non-deterministic To recognize more languages Select the result for converting a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA): The language recognized remains the same The language recognized changes The automaton becomes infinite The automaton becomes non-deterministic Select what regular expressions describe: Finite sets of strings Infinite sets of strings Only numbers Complex data structures Select the condition defining a language as regular if and only if_______ accepted by DFA accepted by PDA accepted by LBA accepted by Turing machine Choose the following statements are correct for a concept called inherent ambiguity in CFL? Every CFG for L is ambiguous Every CFG for L is unambiguous Every CFG is also regular None of these select the situation when a string is accepted by a PDA. Acceptance state All of the mentioned None of the mentioned Present state Select DPDA is defined as a PDA in which: More than one state can have two or more outgoing transitions Atleast one state has more than one transitions None of the mentioned nested word automata Select the purpose of the start state in a DFA: It signifies the end of the DFA It represents the initial configuration of the DFA It indicates the acceptance state It is optional and may not be present Select the distinguishing feature of a DFA compared to a Non-deterministic Finite Automaton (NFA): DFA has multiple start states DFA has a single start state DFA has an infinite number of states DFA has non-unique transitions Select the purpose of an accepting state in a DFA: It signifies the end of the DFA It represents the initial configuration of the DFA It indicates that the DFA has accepted the input string It is optional and may not be present Can a DFA recognize non-regular languages? Yes No Only if it has more than one accepting state Only if it has a large number of states Recall which of the following is true about a DFA\'s transition function? It is not necessary in a DFA It maps a state and an input symbol to a set of states It maps a state and an input symbol to a unique next state It maps an input symbol to a state State the maximum number of states that can be present in a state transition diagram of a DFA: Unlimited Exactly 2 Finite At least 3 Tell what does DFA stand for in the context of computer science? Deterministic Finite Alphabet Deterministic Finite Automata Digital Finite Algorithm Deterministic Finite Analysis Select the minimum number of states required to recognize the language represented by the regular expression (01)*: 1 2 3 4 Select the minimum number of states required to recognize the language represented by the regular expression (ab)*: 1 2 3 4 Identify the full form of NFA : Nondeterministic Final Automaton Non-Finite Automaton Nondeterministic Finite Automaton New Finite Algorithm Recall how many states can an NFA have? Infinite Finite Variable Bounded Select for an NFA, how many transitions can occur for a given input symbol and current state? One Two Multiple None Select which of the following describes an NFA? It can have only one possible transition for a given input symbol and current state. It always moves to a unique state for a given input symbol and current state. It can have epsilon transitions. It has a fixed number of states. Locate in an NFA, what is the initial state? Any state in the set of states The first state in the set of states A designated start state The final state Identify from the following options that is true about an NFA\'s transition function: It maps a state and an input symbol to a set of states. It maps a state and an input symbol to a single state. It maps a set of states and an input symbol to a single state. It maps a state to a set of input symbols. Select whether an NFA can accept strings of infinite length: Yes, always No, never It depends on the NFA Only if it has an infinite number of states Identify the role of the final states in an NFA: They are where the NFA starts processing input strings. They determine whether a string is accepted or rejected. They are the states where the NFA gets stuck. They are not relevant in NFA operations. Identify for an NFA, what does an epsilon transition represent: A transition without consuming any input symbol A transition to the next state in lexicographic order A transition to the final state A transition triggered by an non-empty input string Memorize whether an NFA have no final states? Yes No Only if it has a single initial state Only if it has no transitions Select the primary purpose of the Pumping Lemma: To generate strings in a regular language To prove that a given language is regular To determine the length of strings in a regular language To disprove that a given language is regular Select the correct option for :Which of the following is NOT a step in applying the Pumping Lemma to prove a language is not regular? Assume the language is regular. Choose a string from the language. Pump the string to generate a longer string. Show that the pumped string is not in the language. Select the correct option for :In the context of the Pumping Lemma, what does \"pumping\" refer to? Generating new strings from existing ones in the language Breaking down strings into smaller substrings Adding additional characters to strings Recognizing strings using a finite automaton Identify which of the following is NOT a condition of the Pumping Lemma? The length of the pumped string must be less than or equal to the pumping length. The pumped string must remain in the language after pumping. The language must be regular. The length of the pumped string must be greater than the pumping length. Select the type of languages to which the Pumping Lemma is applicable: Regular languages only Context-free languages only Both regular and context-free languages Neither regular nor context-free languages Select the significance of the "pumping length" (p) in the Pumping Lemma: The non-constant of the pumped string The minimum length of a regular language A constant for a given regular language The maximum length of a regular language Identify the property that is crucial for the Pumping Lemma to hold for a regular language: Pumping property Concatenation property Closure property Closure under union property Recall ,what Pumping Lemma state about regular languages? Every language can be recognized by a finite automaton Every regular language has a pumping length Every regular language has an infinite number of strings Every regular language contains a palindrome Select the requirement for applying the Pumping Lemma to a language: The language must be context-free The language must contain an infinite number of strings The language must be finite The language must be regular Select the key property of regular languages that the Pumping Lemma leverages? Non-determinism Infiniteness Determinism Repetition Select the operation that preserves the regularity of languages: Intersection Union Substitution Kleene star Select from the following statements that is true about the complement of a regular language: The complement of a regular language is always regular. The complement of a regular language is never regular. The complement of a regular language is context-free. The complement of a regular language is context-sensitive. Select the meaning of closure property in the context of regular languages: It refers to the ability of regular languages to be closed under certain operations. It indicates the ability of regular languages to concatenate strings indefinitely. It signifies the closure of regular languages to external modifications. It represents the closure of regular languages to additional symbols. Identify which of the following statements is true about the intersection of regular languages? The intersection of regular languages is always regular. The intersection of regular languages is always context-free. The intersection of regular languages is always context-sensitive. The intersection of regular languages is never regular. Select the purpose of Kleene star operation that is applied to a regular language: It represents the concatenation of two regular languages. It indicates the closure of a regular language under concatenation. It denotes the union of a regular language with its complement. It signifies the closure of a regular language under iteration. Select the property of regular languages that is true regarding their complement: The complement of a regular language is always context-free. The complement of a regular language is never regular. The complement of a regular language is always regular. The complement of a regular language is always context-sensitive. Select the closure property of regular languages that is true regarding union: Regular languages are closed under union. Regular languages are not closed under union. Regular languages have no union operation. Regular languages are closed under concatenation. Select the option which is true about the closure of regular languages under intersection: Regular languages are closed under intersection. Regular languages are not closed under intersection. Regular languages are only partially closed under intersection. Regular languages are closed under union, not intersection. select the operation that is closed under regular languages: Intersection Concatenation Complementation All of the above Identify the property that allows regular languages to be recognized by finite automata: Closure under complementation Closure under concatenation Closure under union Closure under intersection In a Turing machine, Select the significance of the transition function being partial? It allows for non-deterministic computation. It limits the machine's ability to solve certain problems. It defines transitions only for specific states and symbols. It ensures the machine always halts. Recognize the component of a Turing machine that is responsible for determining the next action based on the current state and symbol read? Tape Head Transition function State register Select the purpose of the input alphabet in a Turing machine? To define the set of symbols allowed on the tape. To specify the initial state of the machine. To control the movement of the tape. To determine the next state based on the current state and symbol read. Select the significance of the halting state in a Turing machine? It indicates an error in computation. It marks the end of the computation. It signifies a transition to a new state. It represents an undefined state. Recognize from the following is NOT a characteristic of a Turing machine? Infinite memory tape Finite set of states Finite alphabet of symbols Finite computation time Select the following statements is true regarding the Pumping Lemma for Regular Languages? It applies to all languages. It guarantees that any string in the language can be divided into five parts. It can prove that a language is regular, but not necessarily that a language is not regular. It applies only to context-free languages. Select from following is a correct interpretation of the Pumping Lemma for Regular Languages? It states that every sufficiently long string in the language can be split into parts such that certain properties hold. It guarantees that every string in the language can be pumped to generate an infinite number of strings. It asserts that every language can be generated by a regular expression. It ensures that every regular language can be recognized by a deterministic finite automaton (DFA). Select from the following statements is true regarding the Pumping Lemma for Context-Free Languages? It applies only to regular languages. It can prove that a language is context-free, but not necessarily that a language is not context- free. It applies only to languages generated by regular expressions. It guarantees that every context-free language is decidable. Select from the following, the Pumping Lemma for Context-Free Languages can be used to prove that- The existence of an infinite number of strings in the language. The existence of a regular expression generating the language. The existence of a context-free grammar generating the language. The existence of a context-sensitive grammar generating the language. Choose the main purpose of a context-free grammar? To describe the structure of context-sensitive languages To describe the structure of regular languages To describe the structure of context-free languages To describe the structure of recursively enumerable languages Choose Which of the following is not a component of a context-free grammar? Terminals Variables Lexemes Productions Choose in a context-free grammar, a production rule typically consists of: Terminal symbols Terminal symbols Both terminal and non-terminal symbols Regular expressions Choose which of the following is true about context-free grammars? They can recognize all regular languages. They can generate all regular languages. They can generate some regular languages but not all. They cannot generate any regular languages. Choose the role of non-terminal symbols in a context-free grammar? They represent the basic building blocks of the language. They represent specific strings of characters. They represent variables that can be replaced by other symbols. They represent the final output of the grammar. Select the primary purpose of a pushdown automaton (PDA)? To recognize regular languages To recognize context-free languages To recognize context-sensitive languages To recognize recursively enumerable languages Select the following automata is equivalent to a pushdown automaton? Finite automaton Deterministic finite automaton Turing machine Non-deterministic finite automaton Select the following languages can be recognized by a pushdown automaton? All regular languages All context-free languages All context-sensitive languages All recursively enumerable languages Select the significance of the initial stack symbol in a pushdown automaton? It determines the acceptance of the input string. It represents the bottom of the stack. It determines the start state of the automaton. It represents the top of the stack. Select which component makes a pushdown automaton more powerful than a finite automaton? Input tape Stack Transition function State register Select the following is not a limitation of pushdown automata? They cannot recognize non-context-free languages. They require more memory compared to finite automata. They cannot recognize non-regular languages. They cannot recognize non-context-sensitive languages.