Midterm 2 - COMP 310

4/30/24, 6:59 PM Midterm 2: COMP 310 AUTO LANG+COMPUTN - (16008-SP2024)  This quiz has been regraded; your score was affected. Midterm 2 Due Apr 24 at 12:15pm Points 27 Questions 27 Available Apr 24 at 11am - Apr 24 at 12:15pm 1 hour and 15 minutes Time Limit None This quiz was locked Apr 24 at 12:15pm. Attempt History LATEST Attempt Time Score Regraded Attempt 1 55 minutes 17.5 out of 27 18.5 out of 27 Score for this quiz: 18.5 out of 27 Submitted Apr 24 at 11:54am This attempt took 55 minutes.  Question 1 1 / 1 pts Given language L={anbk, k 2n}. When giving a Pumping Lemma proof that the language is not regular. which of the following selections of string w are allowed (select all that are correct) Correct! w=a2mb4m w=ambm Correct! w=amb3m Correct! w=amb2m w=a2mbm  Question 2 Original Score: 0 / 1 pts Regraded Score: 1 / 1 pts  This question has been regraded. https://canvas.csun.edu/courses/145981/quizzes/524834 1/9 4/30/24, 6:59 PM Midterm 2: COMP 310 AUTO LANG+COMPUTN - (16008-SP2024) Select from the list below all strings that are in the language of the following CFG Correct! 0100110 11001010 You Answered 10001101 00001000 10101101  Question 3 0 / 1 pts If providing a contradiction proof to show that the given language is not regular using pumping lemma, which of the following conditions are considered any m integer we pick, and any string w we pick from the language ... You Answered there exists an m integer, and exists a string w from the language such that ... there exists an m integer, such that for any string w from the language ... Correct Answer any m integer we pick, there exists a string w from the language such that ...  Question 4 0 / 1 pts For a language L, if L* is regular then L is regular You Answered True Correct Answer False  Question 5 0 / 1 pts Select the CFG from the list such that the language of CFG is the last character of are the same characters} https://canvas.csun.edu/courses/145981/quizzes/524834 the first, middle and 2/9 4/30/24, 6:59 PM Midterm 2: COMP 310 AUTO LANG+COMPUTN - (16008-SP2024) You Answered Correct Answer  Question 6 1 / 1 pts All languages accepted by a DFA are context free. Correct! True False  Question 7 1 / 1 pts List all the variables that are not reachable from start variable S https://canvas.csun.edu/courses/145981/quizzes/524834 3/9 4/30/24, 6:59 PM Midterm 2: COMP 310 AUTO LANG+COMPUTN - (16008-SP2024) Your Answer: they are all reachable  Question 8 0.5 / 1 pts What is the language of the following CFG Your Answer: (0n1n)*(1m0m)*  Question 9 1 / 1 pts Provide a string that verifies the ambiguity of the following grammar Your Answer: abc  Question 10 1 / 1 pts https://canvas.csun.edu/courses/145981/quizzes/524834 4/9 4/30/24, 6:59 PM Midterm 2: COMP 310 AUTO LANG+COMPUTN - (16008-SP2024) List all nullable variables of the following Context Free Grammar (do not need to simplify the grammar, just list the variables) Your Answer: C  Question 11 1 / 1 pts Let correct), the . Which of the following statements are correct (select all that are ={a,b} Correct! L isa non-regular language Correct! all options are correct L is context free language that is also regular  Question 12 1 / 1 pts Given language L={anbk, n 2k}. When giving a Pumping Lemma proof that the language is not regular, if the string w=a2mbm is selected then which value of i will bring into contradiction i=2 there does not exist such value of i, that will bring to a contradiction Correct! i=0 i=1 https://canvas.csun.edu/courses/145981/quizzes/524834 5/9 4/30/24, 6:59 PM Midterm 2: COMP 310 AUTO LANG+COMPUTN - (16008-SP2024)  Question 13 1 / 1 pts What is the language of the following grammar Your Answer: the language is any string made up of a and b where there are 2 a's for every b or lambda  Question 14 1 / 1 pts There are regular languages that contain context-free languages as subsets. Correct! True False  Question 15 0 / 1 pts Language has an equal number of ab's and ba's} is none Regular Language and non Context Free Language You Answered Context Free Language and not Regular Language not Context Free and not Regular Language Correct Answer Context Free and Regular Language  Question 16 1 / 1 pts The language is Context Free and non Regular Language Correct! Context Free and Regular Language non Context Free and non Regular Language none https://canvas.csun.edu/courses/145981/quizzes/524834 6/9 4/30/24, 6:59 PM Midterm 2: COMP 310 AUTO LANG+COMPUTN - (16008-SP2024) non Context Free and Regular Language  Question 17 1 / 1 pts For every Context Free language, any subset of it is regular language. True Correct! False  Question 18 0 / 1 pts If L is a language accepted by a nondeterministic finite automata, then L none Correct Answer must be context - free You Answered may or may not be context - free must not be context - free  Question 19 1 / 1 pts The language {0n1n|n>50} has a regular expression True Correct! False  Question 20 1 / 1 pts {anbm, where the alphabet is a, b and n ≥ 0, m ≥ 0}, is a regular language. Correct! True False  Question 21 0 / 1 pts https://canvas.csun.edu/courses/145981/quizzes/524834 7/9 4/30/24, 6:59 PM Midterm 2: COMP 310 AUTO LANG+COMPUTN - (16008-SP2024) If we have CFG in Chomsky Normal Form with start variable S, which of the following production rules can not be in the grammar (might have more than one answer). B -> a Correct Answer B -> Bc You Answered S -> A -> BC S -> BC  Question 22 1 / 1 pts Give a CFG for the following language or where i,j >=0 Your Answer: S -> aAb | aaaBb | lambda A -> aAb | lambda B-> aaaBb | lambda  Question 23 1 / 1 pts If L is generated by a context - free grammar in Chomsky Normal Form, then L must be regular Correct! L can be either regular or non-regular L must be non-regular none  Question 24 1 / 1 pts The language of the given grammar is "all strings with equal number of a’s followed by equal number of b’s " https://canvas.csun.edu/courses/145981/quizzes/524834 8/9 4/30/24, 6:59 PM Midterm 2: COMP 310 AUTO LANG+COMPUTN - (16008-SP2024) True Correct! False  Question 25 0 / 1 pts If L is not a context-free language, then. You Answered none Correct Answer L must be a non-regular language L must be a regular language L must be finite  Question 26 0 / 1 pts If providing a contradiction proof to show that the given language is not regular using pumping lemma, which of the following conditions are considered You Answered any w string we take from the language, there should exist a xyz cut that leads to contradiction Correct Answer there exist a w from the language, for which any xyz cut you consider there should be a contradiction there exist a w from the language, for which there exists a xyz cut that leads to contradiction any w string we take from the language, for which any xyz cut you consider there should be a contradiction  Question 27 1 / 1 pts The following language {02n|n>0} is Correct! Regular language non Context Free language Context Free language that is non regular Quiz Score: 18.5 out of 27 https://canvas.csun.edu/courses/145981/quizzes/524834 9/9