Formal Languages: Definition, Types, and Properties

Question 1

Which of the following sets constitutes a formal language? Select the correct option.

Accepted Answer

The set of all finite strings constructed from the alphabet {0,1}

Answer

The set of all prime numbers

Answer

The set of all English sentences

Answer

The set of all computer programs

Question 2

In a context-free grammar, which symbol marks the commencement of the grammar?

Accepted Answer

A designated symbol serving as the starting symbol

Answer

Any non-terminal symbol

Answer

The leftmost symbol in the grammar

Answer

The rightmost symbol in the grammar

Question 3

Identify the regular expression that represents the language of all strings over the alphabet {a,b} containing at least one 'a'.

Accepted Answer

(a|b)*a

Answer

a+b*

Answer

a*|b

Answer

a(a|b)*

Question 4

What does the Chomsky hierarchy represent in the context of formal language theory?

Accepted Answer

A categorization of formal languages based on their generative capabilities

Answer

A method for constructing formal grammars

Answer

A set of axioms for formal language theory

Answer

A proof technique for formal languages

Question 5

What is the primary function of the pumping lemma in formal language theory?

Accepted Answer

To demonstrate that a language is not regular

Answer

To demonstrate that a language is regular

Answer

To construct a minimal DFA for a language

Answer

To convert a CFG to a regular expression

Question 6

Which problem in formal language theory is considered decidable?

Accepted Answer

The emptiness problem

Answer

The finiteness problem

Answer

The universality problem

Answer

The halting problem

Question 7

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

Accepted Answer

Type 4

Answer

Type 0 (unrestricted grammar)

Answer

Type 1 (context-sensitive grammar)

Answer

Type 2 (context-free grammar)

Question 8

What is the purpose of a start symbol in a formal grammar?

Accepted Answer

To represent the initial non-terminal symbol from which all derivations begin

Answer

To represent the final terminal symbol that all derivations must end with

Answer

To represent the set of all possible strings that can be generated by the grammar

Answer

To represent the set of all non-terminal symbols used in the grammar

Question 9

What is the Chomsky hierarchy?

Accepted Answer

A hierarchy of formal grammars that are classified by their generative power.

Answer

A hierarchy of finite automata that are classified by their acceptance power.

Answer

A hierarchy of Turing machines that are classified by their computational power.

Answer

A hierarchy of programming languages that are classified by their expressiveness.

Question 10

Which type of grammar is used to generate context-free languages?

Accepted Answer

Type 2 (context-free grammar)

Answer

Type 0 (unrestricted grammar)

Answer

Type 1 (context-sensitive grammar)

Answer

Type 3 (regular grammar)

Question 11

What is the relationship between regular expressions and formal languages?

Accepted Answer

Regular expressions are a concise notation for describing regular languages.

Answer

Formal languages are a more general way of representing regular expressions.

Answer

Regular expressions and formal languages are equivalent.

Answer

Regular expressions are only used for describing deterministic finite automata.

Question 12

Which of the following is NOT a type of formal grammar defined by the Chomsky Hierarchy?

Accepted Answer

Type 3

Answer

Type 0

Answer

Type 1

Answer

Type 2

Question 13

What is the main purpose of the Chomsky hierarchy in the study of formal languages?

Accepted Answer

To classify formal grammars based on their generative power.

Answer

To determine the decidability of formal languages.

Answer

To construct efficient parsing algorithms.

Answer

To prove the equivalence of formal languages.

Question 14

Which of the following is NOT a type of finite automaton?

Accepted Answer

Multi-Tape Turing Machine

Answer

Deterministic Finite Automaton

Answer

Non-Deterministic Finite Automaton

Answer

Pushdown Automaton

Question 15

Which aspect of a programming language is best represented using a formal language?

Accepted Answer

Syntax

Answer

Data types

Answer

Semantics

Answer

Libraries

Question 16

Which property applies to context-sensitive languages?

Accepted Answer

Non-closure under intersection operations

Answer

Closure under union operations

Answer

Closure under concatenation operations

Answer

Non-closure under complement operations

Question 17

Which condition is essential for a language to be considered context-free?

Accepted Answer

Possession of a context-free grammar

Answer

Decidability

Answer

Regularity

Answer

Closure under union operations

Question 18

What is a major limitation of finite automata?

Accepted Answer

Inability to recognize context-free languages

Answer

Inability to recognize regular languages

Answer

Inability to recognize context-sensitive languages

Answer

Non-deterministic behavior

Question 19

Which technique is employed to demonstrate that a language is not context-free?

Accepted Answer

Pumping lemma

Answer

Parsing

Answer

Closure properties

Answer

Myhill-Nerode theorem

Question 20

Which language class in the Chomsky hierarchy can define relationships dependent on surrounding elements?

Accepted Answer

Context-sensitive languages

Answer

Regular languages

Answer

Context-free languages

Answer

Unrestricted languages

Question 21

Explain the relationship between regular expressions and finite automata. Provide a concise example showcasing their interplay in practical applications.

Accepted Answer

Regular expressions and finite automata have equivalent expressive power, enabling them to recognize the same set of languages.

Answer

Regular expressions and finite automata are unrelated concepts.

Answer

Finite automata can be used to describe regular expressions, but not vice versa.

Answer

Regular expressions can be used to implement finite automata, while finite automata cannot implement regular expressions.

Question 22

How does the Chomsky hierarchy contribute to our understanding of formal languages?

Accepted Answer

It categorizes languages based on their generative capabilities.

Answer

It provides a practical approach to parsing formal languages.

Answer

It simplifies the analysis of formal languages by reducing their complexity.

Answer

It has no practical applications in computer science.

Question 23

Which of the following is a regular expression for the language L = {w | w is a string over {a, b} that contains an odd number of a's and an even number of b's}

Accepted Answer

(a*b*a*b*)*

Answer

(ab)*

Answer

(a|b)*

Answer

a*b*

Question 24

Which of the following is a context-free grammar for the language L = {w | w is a string over {a, b} that contains a substring abab}

Accepted Answer

S -> aSb | a

Answer

S -> aS | bS | ab

Answer

S -> ab | a | b

Answer

S -> a | b | abab

Question 25

Which of the following is NOT a closure property of regular languages?

Accepted Answer

Reverse

Answer

Union

Answer

Intersection

Answer

Homomorphism

Question 26

Which of the following is a context-sensitive language?

Accepted Answer

The set of all strings over {a, b} that contain at least one palindromic substring

Answer

The set of all strings over {a, b} that contain an odd number of a's and an even number of b's

Answer

The set of all strings over {a, b} that have a length that is a multiple of 3

Answer

The set of all strings over {a, b} that start with an a and end with a b

Question 27

Which statement accurately describes the generative power of regular and context-free grammars?

Accepted Answer

Regular grammars can generate only regular languages, while context-free grammars can generate a wider range of languages, including regular languages.

Answer

Regular grammars can generate all languages, including those generated by context-free grammars.

Answer

Both regular and context-free grammars have equal generative power.

Answer

Context-free grammars can generate only regular languages, while regular grammars can generate a wider range of languages, including context-free languages.

Question 28

In a Turing machine, which component manages state transitions and symbol manipulation on the tape?

Accepted Answer

Control Unit

Answer

Tape

Answer

Head

Answer

Alphabet

Question 29

A regular expression is described by:

Accepted Answer

A concise set of rules and patterns

Answer

A set of production rules

Answer

A hierarchical structure

Question 30

Which of the following is not a closure property of regular languages?

Accepted Answer

Context-sensitivity

Answer

Union

Answer

Intersection

Answer

Kleene star

Question 31

A context-free grammar comprises:

Accepted Answer

A set of production rules and an initial symbol

Answer

A set of regular expressions and an initial symbol

Answer

A hierarchical structure and an initial symbol

Answer

A finite set of patterns and an initial symbol

Question 32

A distinctive feature of a regular grammar is:

Accepted Answer

Production rules that are left-linear or right-linear

Answer

Context-sensitive production rules

Answer

Inherent ambiguity

Answer

Recursive rules

Question 33

A finite automaton consists of:

Accepted Answer

States, transitions, and an initial state

Answer

A hierarchical structure and an initial symbol

Answer

Regular expressions and an initial symbol

Answer

Production rules and an initial symbol

Question 34

Which of the following is not a type of finite automaton?

Accepted Answer

Non-deterministic Turing machine

Answer

Deterministic finite automaton

Answer

Non-deterministic finite automaton

Answer

Mealy machine

Question 35

A decidable problem for formal languages is:

Accepted Answer

Determining if two regular expressions represent the same language

Answer

Predicting whether a Turing machine will halt for a given input

Answer

Establishing if a context-free grammar is ambiguous

Question 36

The pumping lemma for regular languages states that:

Accepted Answer

For any sufficiently long string in a regular language, segments of the string can be repeated to produce another valid string in the language

Answer

Regular languages can be parsed efficiently

Question 37

What type of grammar can generate the language L = {a^n b^n | n ≥ 0}?

Accepted Answer

Context-free grammar

Answer

Type 0 grammar

Answer

Type 2 grammar

Answer

Regular grammar

Question 38

Which of the following is NOT a closure property of regular languages?

Accepted Answer

They are closed under complementation

Answer

They are closed under union

Answer

They are closed under concatenation

Answer

They are closed under intersection

Question 39

What is the Chomsky hierarchy?

Accepted Answer

A hierarchical classification of formal languages based on their generative power

Answer

A hierarchical classification of Turing machines based on their computational power

Answer

A hierarchical classification of finite-state automata based on their recognition power

Question 40

Which type of grammar is used to generate the language L = {w | w contains an odd number of 'a's and an even number of 'b's}

Accepted Answer

Context-sensitive grammar

Answer

Regular grammar

Answer

Type 0 grammar

Question 41

What is the relationship between regular languages and context-free languages?

Accepted Answer

Every regular language is a context-free language, but not every context-free language is a regular language

Answer

Every context-free language is a regular language, but not every regular language is a context-free language

Question 42

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

Accepted Answer

Stochastic grammar

Answer

Type 2 grammar

Answer

Type 0 grammar

Answer

Type 1 grammar

Question 43

A context-free grammar is one in which:

Accepted Answer

The left-hand side of each production rule contains a single non-terminal symbol.

Answer

The right-hand side of each production rule contains a single terminal symbol.

Answer

Every production rule has the same number of symbols on the left-hand side and right-hand side.

Question 44

Which of the following languages is NOT regular?

Accepted Answer

{a^n b^m | n > m}

Answer

{a^n b^n | n >= 0}

Answer

{a^n b^n c^n | n >= 0}

Answer

{a^n b^m | n = m}

Question 45

A Chomsky normal form grammar is a grammar in which:

Accepted Answer

Every production rule is of the form A -> BC, A -> a, or S -> ε.

Answer

Every production rule is of the form A -> aB, A -> Ba, or S -> ε.

Answer

Every production rule is of the form A -> BC, A -> a, or A -> ε.

Question 46

The language generated by the grammar G = ({S, A}, {a, b}, P, S), where P = {S -> aA, S -> bA, A -> aA, A -> bA} is:

Accepted Answer

The set of all strings over {a, b} that contain an equal number of a's and b's.

Answer

The set of all strings over {a, b} that start with an a.

Answer

The set of all strings over {a, b} that end with a b.

Question 47

Which of the following is a property of context-sensitive languages?

Accepted Answer

They are closed under intersection.

Answer

They are closed under union.

Answer

They are closed under complement.

Answer

They are closed under Kleene star.

Question 48

A Turing machine is a theoretical model of computation that consists of:

Accepted Answer

A finite-state control, an infinite tape, and a read/write head.

Answer

A finite-state control, a finite tape, and a read/write head.

Answer

An infinite-state control, an infinite tape, and a read-only head.

Question 49

Which of the following is a decidable problem?

Accepted Answer

The halting problem for deterministic Turing machines.

Answer

The Post correspondence problem.

Answer

The halting problem for non-deterministic Turing machines.

Question 50

Which of the following is NOT a use of formal languages?

Accepted Answer

Natural language processing

Answer

Operating system design

Answer

Compiler design

Answer

Database theory