Practice Questions (Quiz) Flashcards
For any language
L ⊆ Σ∗ , Σ != ∅ there is a deterministic automata M, such that L = L(M).
only when L is regular n
Any finite language is regular
any finite language is a finite union of one element regular
languages
y
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.
basic fact and definition
y
Σ in any Generalized Finite Automaton includes some regular expressions.
definition of GFA; GFA recognizes regular expressions over Σ
y
For any finite automata M, there is a regular expression r, such that
L(M) = r.
main theorem; defined in proof of Main Theorem
y
Pumping Lemma says that we can always prove that a language is
not regular.
PL gives a certain characterization of infinite regular languages; PL serves as a tool for proving that some
languages are not regular
n
Let L be a regular language, and L1 ⊆ L, then L1 is regular
L1 = {a^nb^n : n ≥ 0} is a non-regular subset of regular L = a∗b*
n
Let L be a language. The language L^R = {w^R : w ∈ L} is regular.
L^R is accepted by finite automata M^R constructed from M
such that L(M) = L
y
The class of regular languages is closed with respect to subset relation
Consider
L1 = {a^nb^n : n ∈ N}, L2 = a∗b∗
L1 ⊆ L2 and L1 is a non-regular subset of a regular L2
n
L (over Σ) is regular, so is the language L1 = {xy : x ∈ L, y !∈ L}
L1 = L(Σ∗ − L) and L regular, hence (Σ∗ − L) is regular (closure
under complement), so is L1 by closure under concatenation
y
Show that the language
L = {xyx^R : x, y ∈ Σ∗} is regular for any Σ.
Take x = e ∈ Σ∗. The language
L1 = {eye^R : e, y ∈ Σ∗}⊆ L
and L1 = Σ∗. We get Σ∗ ⊆ L ⊆ Σ∗ and hence L = Σ∗ is regular
Given a context-free grammar G , L(G) = {w ∈ V : S⇒∗Gw}
w ∈ Σ*
n
A language is context-free if and only if it is accepted by a context-free
grammar.
Generated, not accepted
n
Any regular language is a context-free language
- Any Finite Automata is a PDF automata
2.Regular languages are generated by regular grammars, that are also CF.
y
L = {w ∈ {a, b}∗ : w = w^R} is context-free
G with the rules:
S → aSa|bSb|a|b||e y
Any regular language has a finite representation
definition; regular expression is a finite string
y
Given L1, L2 languages over Σ, then ((L1 ∩ (Σ∗ − L2)) ∪ L2)L1 is
regular.
only when both are regular languages
n
Pumping Lemma serves as a tool for proving that a language is not
regular.
when the language is infinite and we can get contradiction
y
L = {w ∈ {a, b}∗ : w = w^R} is regular
not regular, proof by PL
n
L = {a^na^n : n ≥ 0} is not regular.
L = (aa)∗ and hence regular
n
L = {a^nc^n : n ≥ 0} is regular
not regular, proof by PL
n
Let L be a regular language, and L1 ⊆ L, then L1 is regular
L1 = {a^nb^n : n ≥ 0} is a non-regular subset of regular
L = a∗b∗
n
Show that the class of regular languages is not closed with
respect to subset relation.
Consider
L1 = {a^nb^n : n ∈ N}, L2 = a∗b∗
L1 ⊆ L2 and L1 is a non-regular subset of a regular L2
If L1, L2 are regular languages, is L1 ∩ L2 also regular? Explain.
YES, class of regular languages is closed under ∩.
If L1 ∩ L2 is a regular language, are L1 and L2 also regular? Explain.
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
Show that if L is regular, so is the language
L1 = {xy : x ∈ L, y !∈L}.
Observe that L1 = L(Σ∗−L) and L regular, hence Σ∗ − L) is regular
(closure under complement), so is L1 by closure under concatenation.
Any regular language is finite.
L = a∗
is infinite
n
For any language L there is a deterministic automata M, such that
L = L(M).
language must be regular
n
Given L1, L2 regular languages over Σ, then (L1 ∩ (Σ∗ − L1))L2 is
not regular.
Regular languages are closed under intersection and complement
n
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.
only when M is a finite automaton
n
L = {a^2n : n ≥ 0} is regular.
L = (aa)*
y
L = {a^n : n ≥ 0} is not regular.
L = a∗
n
L = {b^na^n : n ≥ 0} is not regular
proved using Pumping Lemma
y
Let L be a regular language. The language L^R = {w^R : w ∈ L} is
regular.
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
Any subset of a regular language is a regular language
L1 = {b^na^n : n ≥ 0} ⊆ L = b∗a∗ and L is regular, and L1
is not regular
n
For any finite language L ⊆ Σ∗,
Σ != ∅ there is a
finite automata M, such that L = L(M).
any finite language is regular
y
Given L1, L2 languages over Σ, then ((L1∪(Σ∗−L2))∩L2) is regular
only when both are regular languages
n
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
only when qj ∈ F
n
If L1 ∩ L2 is a regular language, so are L1 and L2.
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
L = {a^na^n : n ≥ 0} is not regular
L = a^na^n = a^2n = (aa)∗ and hence regular
n
Let L be a regular language, and L1 ⊆ L, then L1 is regular.
L1 = {a^nb^n : n ≥ 0} is a non-regular subset of regular
L = a∗b∗
n
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)))
∃x, y, z ∈ Σ∗
n
Let L be a regular language over Σ != ∅. Then the following holds:
∃w ∈ Σ∗ ∃x, y, z ∈ Σ∗
(w = xyz ∩ y != e ∩ ∀n ≥ 0(xy^nz ∈ L))
only when L is infinite. n
The set of terminals in a context free grammar G is a subset of
alphabet of G
Σ ⊆ V
y
The set of terminals and non- terminals in a context free grammar
G form the alphabet of G
V = Σ ∪ (V − Σ)
y
The set of non-terminals is always non- empty
S ∈ V
y
The set of terminals is always non- empty
Finite set can be empty v
n
L(G) = {w ∈ V : S⇒∗Gw}
w ∈ Σ∗
n
Language is regular if and only if is generated by a regular grammar
(right- linear)
proof in class
y
Every subset of a regular language is a language.
a subset of a set is a set.
y
