Question 1

For the given set of code, the grammar representing real numbers in Pascal has error in one of the six lines. Fetch the error. (1) ->     (2) ->   | epsilon (3) ->    | epsilon (4) -> ‘E’    | epsilon (5) -> + | – | epsilon (6) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9a) 3b) 4c) 2d) No errorsAnswer: aExplanation:   –>       –>   | epsilon   –> ‘.’   | epsilon   –> ‘E’    | epsilon   –> + | – | epsilon   –> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0");    });/**/ advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0");    });/**/        4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS|aA->SbA|ba|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a");    });/**/6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");    });/**/8. Which of the following are context free language?a) L={aibi|i>=0}b) L={wwr| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");    });/**/10.  L->rLt|tLr|t|rThe given grammar produces a language which is:

McqOptions · Accepted Answer

4c) 2d) No errorsAnswer: aExplanation:   –>       –>   | epsilon   –> ‘.’   | epsilon   –> ‘E’    | epsilon   –> + | – | epsilon   –> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0");    });/**/ advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0");    });/**/        4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS|aA->SbA|ba|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a");    });/**/6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");    });/**/8. Which of the following are context free language?a) L={aibi|i>=0}b) L={wwr| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");    });/**/10.  L->rLt|tLr|t|rThe given grammar produces a language which is:a) All palindromeb) All even palindromes

McqOptions · Answer

3b) 4c) 2d) No errorsAnswer: aExplanation:   –>       –>   | epsilon   –> ‘.’   | epsilon   –> ‘E’    | epsilon   –> + | – | epsilon   –> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0");    });/**/ advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0");    });/**/        4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS|aA->SbA|ba|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a");    });/**/6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");    });/**/8. Which of the following are context free language?a) L={aibi|i>=0}b) L={wwr| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");    });/**/10.  L->rLt|tLr|t|rThe given grammar produces a language which is:a) All palindrome

McqOptions · Answer

2d) No errorsAnswer: aExplanation:   –>       –>   | epsilon   –> ‘.’   | epsilon   –> ‘E’    | epsilon   –> + | – | epsilon   –> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0");    });/**/ advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0");    });/**/        4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS|aA->SbA|ba|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a");    });/**/6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");    });/**/8. Which of the following are context free language?a) L={aibi|i>=0}b) L={wwr| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");    });/**/10.  L->rLt|tLr|t|rThe given grammar produces a language which is:a) All palindromeb) All even palindromesc) All odd palindromes

McqOptions · Answer

No errorsAnswer: aExplanation:   –>       –>   | epsilon   –> ‘.’   | epsilon   –> ‘E’    | epsilon   –> + | – | epsilon   –> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0");    });/**/ advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0");    });/**/        4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS|aA->SbA|ba|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a");    });/**/6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");    });/**/8. Which of the following are context free language?a) L={aibi|i>=0}b) L={wwr| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement/**/    var adpushup = adpushup || {};    adpushup.que = adpushup.que || [];    adpushup.que.push(function() {        adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");    });/**/10.  L->rLt|tLr|t|rThe given grammar produces a language which is:a) All palindromeb) All even palindromesc) All odd palindromesd) Strings with same begin and end symbolsAnswer: cExplanation:  As there exists no production for the palindrome set, even palindromes like abba, aabbaa, baaaaaab, etc will not be generated.Sanfoundry Global Education & Learning Series – Automata Theory.To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!Telegram | Youtube | LinkedIn | Instagram | Facebook | Twitter | PinterestYoutube | LinkedIn | Instagram | Facebook | Twitter | Pinterest« Prev - Automata Theory Questions and Answers –  DPDA and Context Free Languages» Next - Automata Theory Questions and Answers –  CFG-Eliminating Useless Symbols

Question 2

State true or false:S-> 0S1|01Statement: No regular expression exists for the given grammar.

McqOptions · Accepted Answer

false

McqOptions · Answer

true

Question 3

CFGs are more powerful than:

McqOptions · Accepted Answer

McqOptions · Answer

DFA

McqOptions · Answer

NDFA

McqOptions · Answer

Mealy Machine

McqOptions · Answer

All of the mentioned

1.	For the given set of code, the grammar representing real numbers in Pascal has error in one of the six lines. Fetch the error. (1) -> (2) -> \| epsilon (3) -> \| epsilon (4) -> ‘E’ \| epsilon (5) -> + \| – \| epsilon (6) -> 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9a) 3b) 4c) 2d) No errorsAnswer: aExplanation: –> –> \| epsilon –> ‘.’ \| epsilon –> ‘E’ \| epsilon –> + \| – \| epsilon –> 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0"); });// advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0"); });// 4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS\|aA->SbA\|ba\|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });//6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });//8. Which of the following are context free language?a) L={aibi\|i>=0}b) L={wwr\| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi\|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });//10. L->rLt\|tLr\|t\|rThe given grammar produces a language which is:
A.	3b) 4c) 2d) No errorsAnswer: aExplanation: –> –> \| epsilon –> ‘.’ \| epsilon –> ‘E’ \| epsilon –> + \| – \| epsilon –> 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0"); });// advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0"); });// 4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS\|aA->SbA\|ba\|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });//6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });//8. Which of the following are context free language?a) L={aibi\|i>=0}b) L={wwr\| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi\|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });//10. L->rLt\|tLr\|t\|rThe given grammar produces a language which is:a) All palindrome
B.	4c) 2d) No errorsAnswer: aExplanation: –> –> \| epsilon –> ‘.’ \| epsilon –> ‘E’ \| epsilon –> + \| – \| epsilon –> 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0"); });// advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0"); });// 4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS\|aA->SbA\|ba\|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });//6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });//8. Which of the following are context free language?a) L={aibi\|i>=0}b) L={wwr\| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi\|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });//10. L->rLt\|tLr\|t\|rThe given grammar produces a language which is:a) All palindromeb) All even palindromes
C.	2d) No errorsAnswer: aExplanation: –> –> \| epsilon –> ‘.’ \| epsilon –> ‘E’ \| epsilon –> + \| – \| epsilon –> 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0"); });// advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0"); });// 4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS\|aA->SbA\|ba\|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });//6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });//8. Which of the following are context free language?a) L={aibi\|i>=0}b) L={wwr\| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi\|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });//10. L->rLt\|tLr\|t\|rThe given grammar produces a language which is:a) All palindromeb) All even palindromesc) All odd palindromes
D.	No errorsAnswer: aExplanation: –> –> \| epsilon –> ‘.’ \| epsilon –> ‘E’ \| epsilon –> + \| – \| epsilon –> 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0"); });// advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0"); });// 4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS\|aA->SbA\|ba\|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });//6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });//8. Which of the following are context free language?a) L={aibi\|i>=0}b) L={wwr\| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi\|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });//10. L->rLt\|tLr\|t\|rThe given grammar produces a language which is:a) All palindromeb) All even palindromesc) All odd palindromesd) Strings with same begin and end symbolsAnswer: cExplanation: As there exists no production for the palindrome set, even palindromes like abba, aabbaa, baaaaaab, etc will not be generated.Sanfoundry Global Education & Learning Series – Automata Theory.To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!Telegram \| Youtube \| LinkedIn \| Instagram \| Facebook \| Twitter \| PinterestYoutube \| LinkedIn \| Instagram \| Facebook \| Twitter \| Pinterest« Prev - Automata Theory Questions and Answers – DPDA and Context Free Languages» Next - Automata Theory Questions and Answers – CFG-Eliminating Useless Symbols
Answer» B. 4c) 2d) No errorsAnswer: aExplanation: –> –> \| epsilon –> ‘.’ \| epsilon –> ‘E’ \| epsilon –> + \| – \| epsilon –> 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0"); });// advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0"); });// 4. Which among the following is incorrect with reference to a derivation tree?a) Every vertex has a label which is a terminal or a variable.b) The root has a label which can be a terminal.c) The label of the internal vertex is a variable.d) None of the mentionedAnswer: bExplanation: The root or interms of the grammar, starting variable can not be a terminal.5. Let G=(V, T, P, S)where a production can be written as:S->aAS\|aA->SbA\|ba\|SSWhich of the following string is produced by the grammar?a) aabbaabb) aabbaac) baababd) None of the mentionedAnswer: bExplanation: The step wise grammar translation can be written as: aAS->aSbaA->aabAS->aabbaaadvertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });//6. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.Which of the following options are correct with respect to the given statements?a) Statement 1 is true but statement 2 is falseb) Statement 1 is false but statement 2 is truec) Both the statements are trued) Both the statements are falseAnswer: cExplanation: One language can more than one grammar. Some can be ambiguous and some cannot.7. Which of the following are non essential while simplifying a grammar?a) Removal of useless symbolsb) Removal of unit productionsc) Removal of null productiond) None of the mentionedAnswer: dExplanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });//8. Which of the following are context free language?a) L={aibi\|i>=0}b) L={wwr\| w is a string and r represents reverse}c) Both (a) and (b)d) one of the mentionedAnswer: aExplanation: None.9. The language L ={ai2bi\|i>=0} is:a) recursiveb) deterministic CFLc) regulard) Two of the mentioned is correctAnswer: dExplanation: The language is recursive and every recursive language is a CFL.advertisement// var adpushup = adpushup \|\| {}; adpushup.que = adpushup.que \|\| []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });//10. L->rLt\|tLr\|t\|rThe given grammar produces a language which is:a) All palindromeb) All even palindromes

2.	State true or false:S-> 0S1\|01Statement: No regular expression exists for the given grammar.
A.	true
B.	false
Answer» B. false

3.	CFGs are more powerful than:
A.	DFA
B.	NDFA
C.	Mealy Machine
D.	All of the mentioned
Answer» E.

Explore topic-wise MCQs in Automata Theory.

State true or false:S-> 0S1|01Statement: No regular expression exists for the given grammar.

CFGs are more powerful than: