Practice Questions (Quiz)

Question 1

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

Answer 1

only when L is regular n

Question 2

Any finite language is regular

Answer 2

any finite language is a finite union of one element regular
languages
y

Question 3

For any deterministic automata M, L(M) = S
{R(1, j, n) : qj ∈ F},
where M has n states with s = q1 and R(1, j, n) is the set of
all strings in Σ∗
that may drive M from state initial state to state qj
without passing through any intermediate state numbered n + 1 or
greater, where n is the number of states of M.

Answer 3

basic fact and definition
y

Question 4

Σ in any Generalized Finite Automaton includes some regular expressions.

Answer 4

definition of GFA; GFA recognizes regular expressions over Σ
y

Question 5

For any finite automata M, there is a regular expression r, such that
L(M) = r.

Answer 5

main theorem; defined in proof of Main Theorem
y

Question 6

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

Answer 6

PL gives a certain characterization of infinite regular languages; PL serves as a tool for proving that some
languages are not regular
n

Question 7

Let L be a regular language, and L1 ⊆ L, then L1 is regular

Answer 7

L1 = {a^nb^n : n ≥ 0} is a non-regular subset of regular L = a∗b*
n

Question 8

Let L be a language. The language L^R = {w^R : w ∈ L} is regular.

Answer 8

L^R is accepted by finite automata M^R constructed from M
such that L(M) = L
y

Question 9

The class of regular languages is closed with respect to subset relation

Answer 9

Consider
L1 = {a^nb^n : n ∈ N}, L2 = a∗b∗
L1 ⊆ L2 and L1 is a non-regular subset of a regular L2
n

Question 10

L (over Σ) is regular, so is the language L1 = {xy : x ∈ L, y !∈ L}

Answer 10

L1 = L(Σ∗ − L) and L regular, hence (Σ∗ − L) is regular (closure
under complement), so is L1 by closure under concatenation
y

Question 11

Show that the language
L = {xyx^R : x, y ∈ Σ∗} is regular for any Σ.

Answer 11

Take x = e ∈ Σ∗. The language
L1 = {eye^R : e, y ∈ Σ∗}⊆ L
and L1 = Σ∗. We get Σ∗ ⊆ L ⊆ Σ∗ and hence L = Σ∗ is regular

Question 12

Given a context-free grammar G , L(G) = {w ∈ V : S⇒∗Gw}

Answer 12

w ∈ Σ*
n

Question 13

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

Answer 13

Generated, not accepted
n

Question 14

Any regular language is a context-free language

Answer 14

1. Any Finite Automata is a PDF automata
   2.Regular languages are generated by regular grammars, that are also CF.
   y

Question 15

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

Answer 15

G with the rules:
S → aSa|bSb|a|b||e y

Question 16

Any regular language has a finite representation

Answer 16

definition; regular expression is a finite string
y

Question 17

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

Answer 17

only when both are regular languages
n

Question 18

Pumping Lemma serves as a tool for proving that a language is not
regular.

Answer 18

when the language is infinite and we can get contradiction
y

Question 19

L = {w ∈ {a, b}∗ : w = w^R} is regular

Answer 19

not regular, proof by PL
n

Question 20

L = {a^na^n : n ≥ 0} is not regular.

Answer 20

L = (aa)∗ and hence regular
n

Question 21

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

Answer 21

not regular, proof by PL
n

Question 22

Let L be a regular language, and L1 ⊆ L, then L1 is regular

Answer 22

L1 = {a^nb^n : n ≥ 0} is a non-regular subset of regular
L = a∗b∗
n

Question 23

Show that the class of regular languages is not closed with
respect to subset relation.

Answer 23

Consider
L1 = {a^nb^n : n ∈ N}, L2 = a∗b∗
L1 ⊆ L2 and L1 is a non-regular subset of a regular L2

Question 24

If L1, L2 are regular languages, is L1 ∩ L2 also regular? Explain.

Answer 24

YES, class of regular languages is closed under ∩.

Question 25

If L1 ∩ L2 is a regular language, are L1 and L2 also regular? Explain.

Answer 25

NO. Take L1 = {a^nb^n : n ∈ N}, L2 = {a^n : n ∈ P rime} L1 ∩ L2 = ∅ is a regular language and L1, L2 are not regular

Question 26

Show that if L is regular, so is the language L1 = {xy : x ∈ L, y !∈L}.

Answer 26

Observe that L1 = L(Σ∗−L) and L regular, hence Σ∗ − L) is regular (closure under complement), so is L1 by closure under concatenation.

Question 27

Any regular language is finite.

Answer 27

L = a∗ is infinite n

Question 28

For any language L there is a deterministic automata M, such that L = L(M).

Answer 28

language must be regular n

Question 29

Given L1, L2 regular languages over Σ, then (L1 ∩ (Σ∗ − L1))L2 is not regular.

Answer 29

Regular languages are closed under intersection and complement n

Question 30

For any M, L(M) = U {R(1, j, n) : qj ∈ F}, where R(1, j, n) is the set of all strings in Σ∗ that may drive M from state initial state to state qj without passing through any intermediate state numbered n + 1 or greater, where n is the number of states of M.

Answer 30

only when M is a finite automaton n

Question 31

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

Answer 31

L = (aa)* y

Question 32

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

Answer 32

L = a∗ n

Question 33

L = {b^na^n : n ≥ 0} is not regular

Answer 33

proved using Pumping Lemma y

Question 34

Let L be a regular language. The language L^R = {w^R : w ∈ L} is regular.

Answer 34

L^R is accepted by a finite automata M^R = (K∪s', Σ, ∆', s', F = {s}), where K is the set of states of M accepting L, s' !∈ K, s the initial state of M, F is the set of final states of M and ∆' = {(r, σ, p) : (p, σ, r) ∈ ∆} ∪ {(s', e, q) : q ∈ F}, where ∆ is the set of transitions of M. y

Question 35

Any subset of a regular language is a regular language

Answer 35

L1 = {b^na^n : n ≥ 0} ⊆ L = b∗a∗ and L is regular, and L1 is not regular n

Question 36

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

Answer 36

any finite language is regular y

Question 37

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

Answer 37

only when both are regular languages n

Question 38

For any deterministic automata M, L(M) = S {R(1, j, n) : qj ∈ K}, where R(1, j, n) is the set of all strings in Σ∗ that may drive M from state initial state to state qj without passing through any intermediate state numbered n+ 1 or greater, where n is the number of states of M

Answer 38

only when qj ∈ F n

Question 39

If L1 ∩ L2 is a regular language, so are L1 and L2.

Answer 39

No, L1 and L2 may not be regular . Take L1 = {a^nb^n : n ∈ N}, L2 = {a^n : n ∈ Prime} L1 ∩ L2 = ∅ is a regular language and L1, L2 are not regular. n

Question 40

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

Answer 40

L = a^na^n = a^2n = (aa)∗ and hence regular n

Question 41

Let L be a regular language, and L1 ⊆ L, then L1 is regular.

Answer 41

L1 = {a^nb^n : n ≥ 0} is a non-regular subset of regular L = a∗b∗ n

Question 42

Let L be a regular language Σ. Then the following condition holds: ∃n ≥ 1 ∀w ∈ L(|w| ≥ n ⇒ ∀x, y, z ∈ Σ∗ (w = xyz∩y != e∩|xy| ≤ n∩∀i ≥ 0(xy^iz ∈ L)))

Answer 42

∃x, y, z ∈ Σ∗ n

Question 43

Let L be a regular language over Σ != ∅. Then the following holds: ∃w ∈ Σ∗ ∃x, y, z ∈ Σ∗ (w = xyz ∩ y != e ∩ ∀n ≥ 0(xy^nz ∈ L))

Answer 43

only when L is infinite. n

Question 44

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

Answer 44

Σ ⊆ V y

Question 45

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

Answer 45

V = Σ ∪ (V − Σ) y

Question 46

The set of non-terminals is always non- empty

Answer 46

S ∈ V y

Question 47

The set of terminals is always non- empty

Answer 47

Finite set can be empty v n

Question 48

L(G) = {w ∈ V : S⇒∗Gw}

Answer 48

w ∈ Σ∗ n

Question 49

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

Answer 49

proof in class y

Question 50

Every subset of a regular language is a language.

Answer 50

a subset of a set is a set. y