Free Printable EECS 510 Midterm 1

1.

A(n) (a) is a finite, nonempty set of symbols usually denoted by

\Sigma.

2.

$\Sigma\ =\ \left\{0,\ 1\right\}$ is the (a) alphabet.

3.

True or False:

The set of all UTF-8 characters, or the set of all printable UTF-8 characters is a common alphabet.

a)

True

b)

False

4.

A(n) (a) is a finite sequence of symbols chosen from an alphabet.

5.

True or False:

A string is sometimes called a 'word'

a)

True

b)

False

6.

The (a) is a string with zero symbols.

7.

True or false:

The empty string is denoted by $\theta$

a)

True

b)

False

8.

True or False:

The empty string is denoted by $\epsilon$

a)

True

b)

False

9.

The length of a string is denoted by:

a)

$\left|s\right|$

b)

$\left|\epsilon\right|$

c)

$s$

d)

$s_1+s_2$

10.

The concatenation of strings $s_1$ and $s_2$ is denoted by:

a)

$s_1\ \cdot\ s_2$

b)

$s_1s_2$

c)

$s_1\ +\ s_2$

d)

$s_1\ \times\ s_2$

11.

True or False: The empty string $\epsilon$ is a string over all alphabets, and is the identity for concatenation: $\epsilon s\ =\ s\epsilon\ =\ s$

a)

True

b)

False

12.

$\Sigma^0\ =\ \left\{\epsilon\right\}$
$\Sigma^1\ =\ \left\{0,\ 1\right\}$
$\Sigma^2\ =\ \left\{00,\ 01,\ 10,\ 11\right\}$
$\Sigma^3\ =\ \left\{000,001,010,011,100,101,110,111\right\}$
$\Sigma^n\$ are the strings of length n over the (a) alphabet

13.

The ___________ of $\Sigma$ is the set of all strings over an alphabet $\Sigma\$

a)

Kleene closure

b)

concatenation

c)

word

d)

language

14.

$\Sigma^?\$ is the set of all strings over an alphabet, while $\Sigma^?$ is the set of all non-empty strings over an alphabet.

a)

+, -

b)

-, +

c)

*, +

d)

+, *

15.

A subset of $\Sigma$ * is called a (a) .

16.

Select the correct ordering of the 5-tuple DFA:

a)

$\left(Q,\ \Sigma,\ \delta,\ q_0,\ F\right)$

b)

$\left(Q,\ \Sigma,\ F,\ \delta,\ q_0\right)$

c)

$\left(Q,\ \Sigma,\ q_0,\ \delta,\ F\right)$

d)

$\left(\Sigma,\ Q,\ q_0,\ \delta,\ F\right)$

17.

Select the correct variable from the 5-tuple DFA:

_____ is a finite, non-empty set of states

a)

$\Sigma$

b)

$Q$

c)

$\delta$

d)

$q_0$

e)

$F$

18.

Select the correct variable from the 5-tuple DFA:

_____ is an alphabet of input symbols

a)

$\Sigma$

b)

$Q$

c)

$\delta$

d)

$q_0$

e)

$F$

19.

Select the correct variable from the 5-tuple DFA:

_____: $Q\times E\longrightarrow Q$ is a transition function

a)

$\Sigma$

b)

$Q$

c)

$\delta$

d)

$q_0$

e)

$F$

20.

Select the correct variable from the 5-tuple DFA:

_____ $\in Q$ is the initial state

a)

$\Sigma$

b)

$Q$

c)

$\delta$

d)

$q_0$

e)

$F$

21.

Select the correct variable from the 5-tuple DFA:

_____ $\subseteq Q$ is the set of accepting states

a)

$\Sigma$

b)

$Q$

c)

$\delta$

d)

$q_0$

e)

$F$

22.

The (a) of a DFA $A=\left(Q,\ \Sigma,\ \delta,\ q_0,\ F\right)$ is denoted by $L\left(A\right)$ and is defined as:

$L\left(A\right)\ :=\left\{w\ \in\Sigma^{\cdot}\ \left|\ \delta`\left(q_0,\ w\right)\in F\ \right|\right\}$

23.

For any language L, if there is a DFA $A$ for which $L=L\left(A\right)$ , then $L$ is said to be a (a) .

24.

(a) is like the deterministic variety except with the ability to explore multiple states "in parallel".

25.

The transition function $\delta$ for an NFA will take a state and a symbol and return a ____________.

a)

set of states

b)

single symbol

c)

set of symbols

d)

single state

26.

An NFA is a 5-tuple $\left(Q,\ \Sigma,\ \delta,\ q_0,\ F\right)$ , like its DFA counterpart, with the one exception being ____, which maps a state and a symbol into the powerset of $Q.$

___: $Q\times\Sigma\longrightarrow P\left(Q\right)$

a)

$Q$

b)

$\Sigma$

c)

$\delta$

d)

$q_0$

e)

$F$

27.

The (a) of the NFA $A$ is $L\left(A\right)$ and is defined as $L\left(A\right):=\left\{w\in\Sigma^{\cdot}\left|\delta'\left(q_0,\ w\ \right)\cap F\ne0\right|\right\}$

28.

For any language $L$ , if $L=L\left(A\right)$ , then we will also say that the language is (a) by the NFA $A$ .

29.

The goal of (a) is to build a DFA $D=\left(Q_D,\ \Sigma_D,\ \delta_D,\ \left\{q_0\right\},\ F_D\right)$ from a given NFA $N=\left(Q_N,\ \Sigma_N,\ \delta_N,\ q_0,\ F_N\right)$ such that $L\left(D\right)=L\left(N\right)$

30.

In subset construction, the initial state $D$ is the (a) set containing only the initial state for $N$ .

31.

A language $L$ is accepted by some DFA if and only if it is accepted by some (a) .

32.

A(n) (a) -transition is one which can be triggered with or without consuming any input.

33.

True or False: In an $\epsilon$ -transition, $\epsilon$ can be a symbol in $\Sigma$ .

a)

True

b)

False

34.

A(n) (a) -NFA is a regular NFA with the transition function augmented to operate on a state and a symbol, or $\epsilon,\ \delta\ :\ Q\times\left(\Sigma\cup\left\{\epsilon\right\}\right)\longrightarrow P\left(Q\right)$

35.

The $\epsilon$ -closure of a state q is (a) (q)

36.

The ________ case of an $\epsilon$ -closure of a state $q$ is defined as $q\in ECLOSE\left(q\right)$

a)

base

b)

recursive

37.

The ________ case of an $\epsilon$ -closure of a state $q$ is defined as $\delta\left(p,\ \epsilon\right)\subseteq ECLOSE\left(q\right)$ for every $p\in ECLOSE\left(q\right)$

a)

base

b)

recursive

38.

A language $L$ is accepted by some $\epsilon$ -NFA if and only if $L$ is accepted by some (a) .

39.

$L^n$ is the language of $n$ words from $L$ ____________ together.

a)

concatenated

b)

added

c)

unioned

40.

$L$ * is the language of _______ or more words from $L$ concatenated together.

a)

zero

b)

one

c)

two

d)

three

41.

A language accepted by some DFA/NFA/ $\epsilon$ -NFA is called a (a) language.

42.

True or False:

Every DFA can be converted into a regular expression, but not every regular expression can be converted into an $\epsilon$ -NFA.

a)

True

b)

False

43.

True or False:

Every DFA can be converted into a regular expression, and every regular expression can be converted into an $\epsilon$ -NFA.

a)

True

b)

False

44.

True or False:

If $L$ is the language accepted by some DFA $A$ , then there is a regular expression $E$ such that $L\left(R\right)=L$

a)

True

b)

False

45.

Every language defined by a regular expression $R$ is also defined by some __________ automaton.

a)

finite

b)

infinite

46.

State the algebraic law:

$\left(R+S\right)+T\ =\ R+\left(S+T\right)$

$\left(RS\right)T\ =\ R\left(ST\right)$

a)

associativity

b)

distributive

c)

annihilator

d)

identity

e)

commutativity

47.

State the algebraic law:

$R+S=S+R$

a)

commutativity

b)

associativity

c)

identity

d)

annihilator

e)

distributive

48.

State the algebraic law:

$0+R=R+0=R$

$\epsilon R=R\epsilon=R$

a)

identity

b)

distributive

c)

annihilator

d)

associativity

e)

commutativity

49.

State the algebraic law:

$0R=R0=0$

a)

annihilator

b)

identity

c)

associativity

d)

commutativity

e)

distributive

50.

State the algebraic law:

$R\left(S+T\right)=RS+RT$

\left(R+S\right)T=RT+ST

a)

annihilator

b)

identity

c)

associativity

d)

commutativity

e)

distributive

51.

State the algebraic law:

$R+R=R$

a)

idempotent

b)

closure laws

52.

State the algebraic law:
( $R$ *)* = $R$ *

0

* =

\epsilon

\epsilon

* =

\epsilon

a)

idempotent

b)

closure laws

53.

Syntactic sugar for one or more copies:

a)

$R^{+\ }:=RR$ * $=R$ * $R$

b)

$R?\ :=\ R+\epsilon$

c)

$R\left\{0\right\}\ :=\ \epsilon$
$R\left\{n+1\right\}=RR\left\{n\right\}$

54.

Syntactic sugar for zero or one copies:

a)

$R^{+\ }:=RR$ * $=R$ * $R$

b)

$R?\ :=\ R+\epsilon$

c)

$R\left\{0\right\}\ :=\ \epsilon$
$R\left\{n+1\right\}=RR\left\{n\right\}$

55.

Syntactic sugar for exactly $n$ copies:

a)

$R^{+\ }:=RR$ * $=R$ * $R$

b)

$R?\ :=\ R+\epsilon$

c)

$R\left\{0\right\}\ :=\ \epsilon$
$R\left\{n+1\right\}=RR\left\{n\right\}$

56.

Let $L$ be a regular language. There exists a constant $n_L$ such that for every string $w\in L$ with $\left|w\right|\ge n_L$ , we can break $w$ into 3 parts $w=$ (a) such that (1) $y\ne\epsilon$ , (2) $\left|xy\right|\le n_L$ , and (3) $xy^kz\in L$ for every $k\in N$

57.

In the following two-player scheme, we use the (a) to show that languages are not regular:

1. We pick that language $L$ which we believe is not regular.

2. The opponent chooses a value for $n_L$

3. We choose the word

w

whose length is at least

n_L

4. The opponent gets to split

w

into 3 parts

x,\ y,

and

z

, but we know that

y\ne\epsilon

and

\left|xy\right|\le n_L

5. Finally, we must show that some string of the form

xy^kz\ \notin L

for some

k\in N

58.

If $L$ and $M$ are regular languages over an alphabet $\Sigma$ , then so is $L\$ ___ $M$

a)

$\cup$

b)

$\cap$

59.

True or False:

If $L$ and $M$ are regular languages over the same alphabet, then so are $L\cdot M$ and $L$ *

a)

True

b)

False

60.

True or False:

If $L$ is a regular language, then so is it complement $L^C$

a)

True

b)

False

61.

If $L$ and $M$ are regular languages over the same alphabet, then so are $L$ __ $M$ and $L$ __ $M$

a)

$\cup;\$ \

b)

$\cup;\ \cap$

c)

$\cap;\$ \

62.

By DeMorgan's laws,

$L$ __ $M\ =\ \left(L^C\cup M^C\right)^C$

a)

$\cap$

b)

$\cup$

c)

\

63.

$L$ __ $M\ =\ L\cap M^C$

a)

\

b)

$\cup$

c)

$\cap$

64.

The _________ of a string $a_1a_2...a_n$ is the string $a_n...a_2a_1$ . We denote the ________ of string $w$ as $w^R$

(a)

65.

The (a) of language $L$ is $L^R$ which is the language whose strings are the reverse of strings in $L$

66.

True or False:
If $L$ is a regular language, then so is $L^R$

a)

True

b)

False

67.

For alphabets $\Sigma$ and $T$ , a function $h\ :\ \Sigma\longrightarrow T$ * induces a (a) on strings $h\ :\ \Sigma$ * $\longrightarrow T$ * defined as $h\left(w\right)\ :=\ h\left(a_1\right)h\left(a_2\right)...h\left(a_n\right)$ for any string $w\ =\ a_1a_2...a_n$ over $\Sigma$

68.

True or False:
If $L$ is a regular language over $\Sigma$ , and $h$ is a string homomorphism from $\Sigma$ , then $h\left(L\right):=\left\{h\left(w\right)\left|w\in L\right|\right\}$ is also a regular language.

a)

True

b)

False

69.

True or False:
Let $h$ be a string homomorphism from alphabet $\Sigma$ to $T$ . If $L$ is a regular language over $T$ , then $h^{-1}\left(L\right)$ is also regular over $\Sigma$

a)

True

b)

False

EECS 510 Midterm 1

Total questions: 69

Worksheet time: 47mins

Similar Resources on Wayground