Practice Questions (Lectures)

Question 1

For any language L ⊆ Σ∗, Σ != ∅
there is a deterministic
automata M, such that L = L(M)

Answer 1

True only when L is regular

Question 2

Any regular language has a finite representation.

Answer 2

True by definition of regular language and the fact that regular
expression is a finite string

Question 3

Any finite language is regular

Answer 3

True as we proved it

Question 4

Given L1, L2 languages over Σ, then
((L1 ∩ (Σ∗ − L2)) ∪ L2)L1 is a regular language

Answer 4

True only when both are regular languages

Question 5

For any finite automata M
L(M) =
U{R(1, j, n) : qj ∈ F}

Answer 5

True only when M has n states and they are put in 1-1
sequence and q1 = s

Question 6

Σ in any Generalized Finite Automaton includes some
regular expressions

Answer 6

True by definition

Question 7

Pumping Lemma says that we can always prove that a
language is not regular

Answer 7

False PL serves as a tool for proving that some
languages are not regular

Question 8

L = {a^n c^n : n ≥ 0} is regular

Answer 8

False we proved by PL that it is not regular

Question 9

The set of terminals in a context free grammar G is a
subset of the alphabet of G

Answer 9

True By definition: Σ ⊆ V

Question 10

The set of terminals and non- terminals in a context free
grammar G form the alphabet of G

Answer 10

True By definition: V = Σ ∪ (V − Σ)

Question 11

The set of non-terminals is always non- empty

Answer 11

True By definition:
S ∈ V

Question 12

The set of terminals is always non- empty

Answer 12

False Σ = ∅ is a finite set

Question 13

Let G be a context-free grammar
L(G) = {w ∈ V :
S∗⇒G w}

Answer 13

False Should be
w ∈ Σ∗

Question 14

The language L ⊆ Σ∗
is context-free if and only if L = L(G)

Answer 14

False Holds only when G is a context -free grammar

Question 15

A language is context-free if and only if it is accepted by a context-free grammar

Answer 15

False Language is generated, not accepted by a grammar

Question 16

Any regular language is context-free

Answer 16

True: Regular languages are generated by regular
grammars, that are special case of CF grammars

Question 17

Language is regular if and only if it is generated by
a regular grammar (right- linear)

Answer 17

True : Theorem proved in class

Question 18

L = {w ∈ {a, b}∗ :
w = w^R } is context-free

Answer 18

True: G with the rules:
S → aSa|bSb|a|b||e is the required grammar

Question 19

A regular language is a CF language

Answer 19

True: Regular grammar is a special case of a context-free
grammar