Question

Problem 1. (10 points) For each of the following statements determine whether it is true or false. * (+1 for correct, 0 for blank, -0.5 for incorrect) The grammar SaSb generates {w € {a,b}" : #a = #b}. T F A CFG is ambiguous if there is exactly one parse tree for every word. TF Two different CFGs could generate two different languages. T F An NPDA could have no final states and still accept the word abba. T F The intersection of two context free languages must be context free. T F A context free language must be finite. T F Some CFGs contain the production a → SX. T F There is an NPDA that accepts {w € {a,b}" : 2#a > #b}. T F When running a word w on an NPDA there could be 2 possible paths. T F I learned so much more because this class used distance learning, т F

Answer 1

1. True

because every time S will replace by aSb so number of 'a' must be equal to number of 'b'.

2. False

A CFG is said to be ambiguous if it has a string having more than one parse tree.

3.True.

Two different CFG could generate two different language.

Example.1. P: A->aA, A->abc , Language= {A,P,{a,b,c}}

2. P: S->aSb, Language = {P,S,{a,b}*}

Two CFG are different also there corresponding language also different.

4.False. There is no way to accept or reject the string without knowing the final state.

5. False.

CFL are not closed under intersection. so, Intersection of two contex free languages not always Context Free.

6. True.

A Context free language must be finite because automata is constructed using context free language and consist of only finite state. if the language is infinite, not able to construct an automata from it. so l=context free language must be finite.

7.False. a-SX this type of CFG is not possible beacause rules for constructing CFG states that set of terminal or non-terminal must be on the right side and and the replacable symbol must be on left side. Here S X are replaceable symbol so they must be on left sie.

Note: Not mentioned how much parts are required to solve . Hence given answer for first 7.