Home › Quizzes › Formal Languages and Grammars

Formal Languages and Grammars

This quiz is designed to assess your understanding of formal languages and grammars, which are fundamental concepts in computer science and linguistics.

15 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

What is a formal language?

  1. A set of strings that can be generated by a grammar
  2. A set of strings that can be recognized by a finite automaton
  3. A set of strings that can be parsed by a context-free grammar
  4. A set of strings that can be translated by a compiler
Question 2 Multiple Choice (Single Answer)

What is the Chomsky hierarchy?

  1. A classification of formal languages based on their generative power
  2. A classification of formal languages based on their recognition power
  3. A classification of formal languages based on their parsing power
  4. A classification of formal languages based on their translation power
Question 3 Multiple Choice (Single Answer)

Which of the following is not a type of formal grammar?

  1. Regular grammar
  2. Context-free grammar
  3. Context-sensitive grammar
  4. Unrestricted grammar
Question 4 Multiple Choice (Single Answer)

What is the difference between a regular grammar and a context-free grammar?

  1. Regular grammars can generate only finite languages, while context-free grammars can generate infinite languages.
  2. Regular grammars can generate only regular languages, while context-free grammars can generate context-free languages.
  3. Regular grammars can generate only context-free languages, while context-free grammars can generate context-sensitive languages.
  4. Regular grammars can generate only context-sensitive languages, while context-free grammars can generate unrestricted languages.
Question 5 Multiple Choice (Single Answer)

What is the pumping lemma for regular languages?

  1. For any regular language L, there exists a constant n such that every string in L of length at least n can be pumped.
  2. For any regular language L, there exists a constant n such that every string in L of length at least n can be pumped twice.
  3. For any regular language L, there exists a constant n such that every string in L of length at least n can be pumped three times.
  4. For any regular language L, there exists a constant n such that every string in L of length at least n can be pumped four times.
Question 6 Multiple Choice (Single Answer)

What is the Chomsky-Schützenberger theorem?

  1. Every context-free language is a regular language.
  2. Every regular language is a context-free language.
  3. Every context-free language is a context-sensitive language.
  4. Every context-sensitive language is an unrestricted language.
Question 7 Multiple Choice (Single Answer)

What is the difference between a context-sensitive grammar and an unrestricted grammar?

  1. Context-sensitive grammars can generate only context-sensitive languages, while unrestricted grammars can generate unrestricted languages.
  2. Context-sensitive grammars can generate only unrestricted languages, while unrestricted grammars can generate context-sensitive languages.
  3. Context-sensitive grammars can generate only context-free languages, while unrestricted grammars can generate context-sensitive languages.
  4. Context-sensitive grammars can generate only regular languages, while unrestricted grammars can generate context-free languages.
Question 8 Multiple Choice (Single Answer)

What is the Greibach normal form for context-free grammars?

  1. A context-free grammar in which every production rule is of the form A -> aB or A -> a
  2. A context-free grammar in which every production rule is of the form A -> BC or A -> a
  3. A context-free grammar in which every production rule is of the form A -> aBC or A -> a
  4. A context-free grammar in which every production rule is of the form A -> BC or A -> aB
Question 9 Multiple Choice (Single Answer)

What is the Cocke-Younger-Kasami algorithm?

  1. An algorithm for parsing context-free grammars
  2. An algorithm for generating context-free grammars
  3. An algorithm for recognizing context-free grammars
  4. An algorithm for translating context-free grammars
Question 10 Multiple Choice (Single Answer)

What is the Earley algorithm?

  1. An algorithm for parsing context-free grammars
  2. An algorithm for generating context-free grammars
  3. An algorithm for recognizing context-free grammars
  4. An algorithm for translating context-free grammars
Question 11 Multiple Choice (Single Answer)

What is the difference between a deterministic context-free grammar and a non-deterministic context-free grammar?

  1. Deterministic context-free grammars can generate only deterministic languages, while non-deterministic context-free grammars can generate non-deterministic languages.
  2. Deterministic context-free grammars can generate only non-deterministic languages, while non-deterministic context-free grammars can generate deterministic languages.
  3. Deterministic context-free grammars can generate only context-free languages, while non-deterministic context-free grammars can generate context-sensitive languages.
  4. Deterministic context-free grammars can generate only context-sensitive languages, while non-deterministic context-free grammars can generate unrestricted languages.
Question 12 Multiple Choice (Single Answer)

What is the CYK algorithm?

  1. An algorithm for parsing context-free grammars
  2. An algorithm for generating context-free grammars
  3. An algorithm for recognizing context-free grammars
  4. An algorithm for translating context-free grammars
Question 13 Multiple Choice (Single Answer)

What is the difference between a regular expression and a context-free grammar?

  1. Regular expressions can generate only regular languages, while context-free grammars can generate context-free languages.
  2. Regular expressions can generate only context-free languages, while context-free grammars can generate regular languages.
  3. Regular expressions can generate only context-sensitive languages, while context-free grammars can generate unrestricted languages.
  4. Regular expressions can generate only unrestricted languages, while context-free grammars can generate context-sensitive languages.
Question 14 Multiple Choice (Single Answer)

What is the Myhill-Nerode theorem?

  1. A theorem that states that every regular language is a deterministic language.
  2. A theorem that states that every context-free language is a deterministic language.
  3. A theorem that states that every context-sensitive language is a deterministic language.
  4. A theorem that states that every unrestricted language is a deterministic language.
Question 15 Multiple Choice (Single Answer)

What is the Kleene star operation?

  1. An operation that concatenates two strings together.
  2. An operation that repeats a string any number of times.
  3. An operation that reverses a string.
  4. An operation that complements a string.
← Back to Quizzes