CECS 329 Final

Which statement about the cardinalities of the set of natural numbers N = {1, 2, 3, ... } and the set of even natural numbers 2N = {0, 2, 4, 6, ... } is correct?

a. |N| < |2N|

b. |N| = |2N|

c. |N| > |2N|

d. The cardinalities |N| and |2N| are incomparable

b. |N| = |2N|

Which statement about the cardinalities of the set A and its power set P(A) is correct?

a. The cardinalities |A| and |P(A)| are incomparable

b. |A| = |P(A)|

c. |A| > |P(A)|

d. |A| < |P(A)|

d. |A| < |P(A)|

How are the cardinalities of the sets N of natural numbers, Q of rational numbers, and R of real numbers related to each other?

a. |N| = |Q| = |R|

b. |N| < |Q| = |R|

c. |N| = |Q| < |R|

d. |N| < |Q| < |R|

c. |N| = |Q| < |R|

Let Σ be an alphabet. A language A ∈ Σ * is called regular if there is a finite automaton M such that...

a. A is the language of M.

b. All the other options are correct.

c. M recognizes A.

d. A=L(M).

b. All other options are correct.

Regular languages are closed under union.

a. True

b. This depends on the language.

c. False

d. This is unknown.

a. True

Write the language of all sequences of characters from Σ = { 0, 1 } that contain two consecutive 1s as a regular expression

a. (0 o 1) U 1 U 1 U (0 o 1)

b. 0 o 1 o 1 o 0

c. (0 U 1) o 1 o 1 o (0 U 1)

d. (0 U 1) o (1 o 1) o (0 U 1)*

c. (0 U 1)* o 1 o 1 o (0 U 1)

All languages are regular.

a. No

b. This is still an open problem.

c. Yes

a. No

The Pumping Lemma can be used to

a. ...prove that a language is not regular.

b. ...prove that a language is regular.

c. ...prove that DFAs are equivalent to NFAs.

a. ...prove that a language is not regular

GNFAs, NFAs, and DFAs are all equivalent, i.e. they all recognize the same class of languages

a. No, NFAs can recognize more languages than DFAs.

b. No, GNFAs can recognize more languages thyan NFAs.

c. Yes, they all recognize regular languages.

d. No, GNFAs can recognize more languages than DFAs.

c. Yes, they all recognize regular languages.

Are all context-free grammars regular?

a. No.

b. Yes.

c. This is unknown.

a. No

Which of these are Context Free Grammars?

C1: S → RRR → 0R1 | ε

C2: S → 0R1R0R → 0R1 | ε

a. C1

b. Neither

c. C2

d. Both C1 and C2.

a. C1

Which of the following languages is context free but not regular?

a. { 0^k 1^k | k ∈ N}

b. {0,1}∗

c. {0,1}∗11{0,1}∗

a. 0^k 1^k | k ∈ N

Decidability of languages does not depend on the model of computation.

False

This is an open problem

True

True

Recall our first proof of the theorem that regular languages are closed under intersection and union: We constructed a new DFA M based on the two DFAs M1 and M2 . The new DFA M used pairs of states M1 and M2 . Given that M1 and M2 have k1 and k2 states respectively. What is the number of states of M ?

a. k21 + k22

b. k1 * k2

c. k1 + k2

b. k1 * k2

What does NFA N1 do on input aab ?

a. Both Accept and Reject

b. Reject

c. Accept

a. Accept

In our proof of the theorem that languages recognized by NFAs are regular we constructed a DFA M' based on an NFA M using the powerset of the states of M. If M has n states, how many states does M' have by this construction?

a. n^2

b. 2^n

c. 2n

b. 2^n

The Pumping Lemma for regular languages depends on the fact that if the DFA M has p states and it runs for more than p steps then M will enter some state at least twice. We call that fact:

a. Goldbach's Conjecture

b. Zorn's Lemma

c. Burnside's Counting Theorem

d. The Pigeonhole Principle

d. The Pigeonhole Principle

We used the Pumping Lemma to show that D = {0^k 1^k| k ≥ 0} is not regular. How can we show that B = {w | w has equal numbers of 0s and 1s} is not regular?

a. We know that 01 is regular. If we assume that B is regular, then 01 U B = D should be regular as well

b. We know that 01 is regular. If we assume that B is regular, then 01 ∩ B = D should be regular as well

c. We cannot because B is regular

d. We know that 01 is not regular. If we assume that B is not regular, then 01 ∩ B = D should not be regular as well

b.. We know that 0 1 is regular. If we assume that B is regular, then 0 1 ∩ B = D should be regular as well

Check all of the strings that are in L(G2)

a. 000111

b. 001101

c. 1010

d. ε

001101, ε, 000111

Match the recognizer with the generator

DFA:

NFA:

PDA:

DFA -> Regular expression

NFA -> Regular expression

PDA -> Context free grammar

Recall the pumping lemma for CFLs:

Let Σ = {0,1} and F = {ww | w ∈ Σ*}

In order to show that F is not context free, which value should we use for the string s to find a contradiction?

a. s1 = 0^p10^p1 ∈ F

b. s2 = 0^p 1^p 0^p 1^p ∈ F

c. s0 = 0^p1^p ∈ F

b. s2 = 0^p 1^p 0^p 1^p ∈ F

Let A1 = {0k1 k2 l| k, l ≥ 0} (equal #s of 0s and 1s).

Let A2 = {0l1 k2 k| k, l ≥ 0} (equal #s of 1s and 2s).

Observe that PDAs can recognize A1 and A2 . What can we now conclude?

a. The class of CFLs is closed under complement.

b. The Pumping Lemma shows that A1 U A2 is not a CFL.

c. The class of CFLs is not closed under intersection.

c. The class of CFLs is not closed under intersection.

Regular languages are closed under intersection.

a. False

b. True

c. This depends on the language

d. This is unknown

b. True

Regular languages are closed under union.

a. This depends on the language

b. False

c. This is unknown

d. True

d. True

Regular languages are closed under concatenation.

a. False

b. True

c. This is unknown.

d. This depends on the language.

b. True

Regular languages are closed under Kleene-*

a. This depends on the language.

b. False

c. True

d. This is unknown

c. True

Context free languages are closed under intersection.

a. False

b. This is unknown.

c. This depends on the language.

d. True

a. False

Context free languages are closed under union.

a. True

b. False

c. This depends on the language.

d. This is unknown.

a. True

Context free languages are closed under concatenation.

a. This depends on the language

b. True

c. False

d. This is unknown

b. True

Context free languages are closed under Kleene-*.

a. This depends on the language.

b. True

c. False

d. This is unknown

b. True

Regular languages are closed under complement.

a. True

b. False

c. This is unknown.

d. This depends on the language.

a. True

Which DFA accepts string aabb ?

a. Both M1 and M2

b. M1 but not M2

c. M2 but not M1

d. Neither M1 nor M2

c. M2 but not M1

Can you show that every NFA can be converted to an equivalent one that has a single accept state?

a. Yes, by adding a new state q and an ε-transition from q to the original start state. Then adding ∈-transitions from every accept state to q. The new state q will be the single accept state of the new NFA.

b. No, because this can't be done in general.

c. Yes, by adding a new state q and then adding ε-transitions from each accept state to q . The new state q will be the single accept state of the new NFA.

d. Yes, by converting it into a DFA.

c. Yes, by adding a new state q and then adding ε-transitions from each accept state to q . The new state q will be the single accept state of the new NFA.

Which regular expression generates the language recognized by the above DFA?

a. (bb)a(aa)

b. b(bb)(aa)

c. b(bb)a(aa)

d. a(aa)(bb)

b. b(bb)(aa)

Swapping the accepting and non-accepting states of a DFA shows that regular languages are closed under complement. Swapping the accepting and non-accepting states of an NFA doesn't necessarily yield an NFA that recognizes the complement. Does that indicate that the class of languages recognized by NFAs is not closed under complement?

a. Yes

b. This depends on the language.

c. This is an open problem.

d. No, since NFAs and DFAs both recognize the same class of languages.

No, since NFAs and DFAs both recognize the same class of languages.

Match the below NFAs with the corresponding regular expressions.

1. a

2. b

3. a*

4. aa*

5. ab

6. (ab*)

7. ab(ab*)

8. a ∪ ab(ab*)

What is the definition of an alphabet Σ ?

a. Σ is a set.

b. Σ is a non-empty, finite set.

c. Σ is a finite set.

d. Σ is a non-empty set.

Σ is a non-empty, finite set.

Regular languages are closed under intersection.

a. True

b. This depends on the language.

c. False

d. This is unknown.

a. True

All languages are regular.

No

The Pumping Lemma can be used to

prove that a language is not regular

What does the Church-Turing-Thesis say?

a. Any real-world computation can be translated into an equivalent computation performed by a Turing machine.

b. The λ-calculus can compute more than the Turing machine.

c. The Halting-Problem of the Turing machine is undecidable.

d. The Turing machine can compute more than the λ-calculus.

a. Any real-world computation can be translated into an equivalent computation performed by a Turing machine.

Which of the following languages are decidable?

a. EQDFA = { | A and B are DFAs and L(A) = L(B)}

b. ADFA = { | B is a DFA and B accepts w}

c. ATM = { | M is a TM and M accepts w }

d. ANFA = { | B is a NFA and B accepts w}

a. EQDFA = { | A and B are DFAs and L(A) = L(B)}

b. ADFA = { | B is a DFA and B accepts w}

d. ANFA = { | B is a NFA and B accepts w}

What is a Turing machine?

a. An early computing device invented by Alan Turing.

b. A theoretical machine to model and reason about computation.

c. A device invented by Alan Turing to discriminate humans from computers.

d. A machine created by Alan Turing to decipher Enigma codes.

b. A theoretical machine to model and reason about computation.

The complexity class P does depend on the model of computation

Yes, but it is equivalent for all reasonable deterministic models of computation.

Languages in P can be efficiently decided

a. Not at all, problems in P generally have a high time complexity.

b. Yes, that's the meaning of the class P.

c. Not necessarily. The time complexity might be O(n^k) with a very large value for k

c. Not necessarily. The time complexity might be O(n^k) with a very large value for k

Which of the following statements are correct (mark all that apply):

a. All languages in P are decidable

b. All regular languages are in the complexity class P

c. All decidable languages are in the complexity class P.

d. All languages in P are T-recognizable.

a. All languages in P are decidable

b. All regular languages are in the complexity class P

d. All languages in P are T-recognizable.

What is the definition of the Bachmann-Landau big O notation?

f(n)∈O(g(n))⟺

a. ∃k>0∀n0∃n>n0:|f(n)|≥kg(n)

b. ∀k>0∃n0∀n>n0:|f(n)|

d. ∃k1>0∃k2>0∃n0∀n>n0:k1g(n)≤f(n)≤k2g(n)

c. ∃k>0∃n0∀n>n0:|f(n)|≤kg(n)

What are the known relationships between the complexity classes P and NP

a. NP ⊆ P

b. P ⊆ NP

c. P ≠ NP

d. P = NP

b. P ⊆ NP

What is the definition of mapping reducibility (also called many-one reducibility)?

The language A⊆Σ∗ is mapping reducible to the language B⊆Γ∗ and we write A≤mB

a. if there is a computable function f:Σ∗→Γ∗ such that w∈B⟺f(w)∈A.

b. if there is a computable function f:Γ∗→Σ∗ such that w∈B⟺f(w)∈A.

c. if there is a computable function f:Σ∗→Γ∗ such that w∈A⟺f(w)∈B.

d. if there is a computable function f:Γ∗→Σ∗ such that w∈A⟺f(w)∈B.

c. if there is a computable function f:Σ∗→Γ∗ such that w∈A⟺f(w)∈B.

Is it true that TIME(t(n)) ⊆ SPACE(t(n))?

a. No, time and space complecity are unrelated

b. Yes, because the tape of a Turing machine has a fixed size

c. Not necessarily, this is yet unknown

d. Yes, because we need at least one computational step to write into a new memory cell.

d. Yes, because we need at least one computational step to write into a new memory cell.

A language B is NP-Complete iff

a. B is not in NP and no language A in NP can be polynomially reduced to B.

b. B is not in NP and any language A in NP can be polynomially reduced to B.

c. B is in NP and no language A in NP can be polynomially reduced to B.

d. B is in NP and any language A in NP can be polynomially reduced to B.

d. B is in NP and any language A in NP can be polynomially reduced to B.

Which of these languages are NP-Complete?

a. 3-SAT (3-CNF Boolean Satifiability)

b. HALT (Halting Problem)

c. PATH (Path Problem)

d. SAT (Boolean Satifiability)

a,d 3-SAT (3-CNF Boolean Satifiability), SAT (Boolean Satifiability)

What does NFA N1 do on input aab ?

Accept

A language A ⊆ Σ ∗ is polynomial time reducible to the language B ⊆ Γ ∗ and we write A ≤p B

a. if there is a computable function f: Σ∗ → Γ∗ such that w ∈ A <=> f(w) ∈ B.

b. if there is a function f : Σ∗ → Γ∗ computable in polynomial time such that w ∈ A <=> f(w) ∈ B .

c. if there is a polynomial f: Σ∗ → Γ∗ such that w ∈ A <=> f(w) ∈ B.

d. if there is a function f: Σ∗ → Γ∗ such that w ∈ A <=> f(w) ∈ B.

b. if there is a function f : Σ∗ → Γ∗ computable in polynomial time such that w ∈ A <=> f(w) ∈ B .

If we would find a proof for SAT ∈ P then this would imply that

a. P ≠ NP

b. P ⊂ NP

c. P = NP

d. P ⊃ NP

c. P = NP

Are all regular languages in the complexity class P ?

a. No, because a PDA might not halt.

b. No, because a DFA reads one input symbol per state transition.

c. No, because an NFA could take exponential time to accept.

d. Yes, because a DFA reads one input symbol per state transition.

d. Yes, because a DFA reads one input symbol per state transition.

How can we describe the complexity classes P and NP informally?

a. NP = All languages where we can guess membership quickly.

P = All languages where we can test membership quickly

b. NP = All languages where we can verify membership quickly.

P = All languages where we can guess membership quickly

c. NP = All languages where we can verify membership quickly.

P = All languages where we can test membership quickly

d. NP = All languages where we can verify membership quickly.

P = All languages where we cannot test membership quickly

c. NP = All languages where we can verify membership quickly.

P = All languages where we can test membership quickly

Which of the following boolean expressions are in 3-CNF?

a. (u ∨ y! ∨ z) ∧ (x ∨ v ∨ z) ∧ (x ∨ y! ∨ w!)

b. (x ∨ y! ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y! ∨ z!)

c. (u ^ y! ^ z) V (x ^ v ^ z) V (x ^ y! ^ w!)

d. (x ^ y! ^ z) V (x ^ y ^ z) V (x ^ y! ^ z!)

a. (u ∨ y! ∨ z) ∧ (x ∨ v ∨ z) ∧ (x ∨ y! ∨ w!)

b. (x ∨ y! ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y! ∨ z!)

Is SAT NP-complete?

a. Only if P=NP

b. This is unkown

c. Yes

d. No

c. Yes

Two models of computation are polynomially related if each can simulate the other with a polynomial overhead, i.e. if the computation takes t(n) time on one model it may take t k(n) time on the other model, for some k .

Which of the following are polynomially related to a 1-tape Turing Machine?

a. cellular automata

b. random access machines (RAM)

c. multi-dimensional Turing Machines

d. multi-tape TMs

a,b,c,d: random access machines (RAM), multi-dimensional Turing Machines, multi-tape TMs, cellular automata

Alan Turing proved the undecidability of the halting problem. Which proof technique from set theory did inspire Turing?

a. Feynman's technique

b. Cantor's diagonal argument

c. Newton's method

d. Zorn's lemma

b. Cantor's diagonal argument

What is the output (on the tape) of the Turing Machine M on input 10010111 where

a. 10011000

b. 01101001

c. 01100111

d. 10010110

a. 10011000

Is the complexity class P closed under union, ie. does L1 ∈ P and L2 ∈ P imply that L1 ∪ L2 ∈ P?

a. This is unknown

b. No

c. Yes

c. Yes

Is the following formula satisfiable? (x ∨ y) ∧ (x ∨ y!) ∧ (x! ∨ y) ∧ (x! ∨ y!)

a. Yes

b. No

b. No

Which of the following are true?

a. n^2 ∈ O(n)

b. 2n ∈ O(n)

c. n log n ∈ O(n^2)

d. 3^n ∈ 2^O(n)

b. 2n ∈ O(n)

c. n log n ∈ O(n^2)

d. 3^n ∈ 2^O(n)

Recall the pumping lemma for CFLs:

Let Σ = {0,1} and F = {ww | w ∈ Σ*}In order to show that F is not context free, which value should we use for the string s to find a contradiction?

a. s1 = 0^p10^p1 ∈ F

b. s2 = 0^p 1^p 0^p 1^p ∈ F

c. s0 = 0^p1^p ∈ F

b. s2 = 0^p 1^p 0^p 1^p ∈ F

Match the Bachmann-Landau asymptotic notation with the correct definition:

a) eK > 0En0 Vn > n0: |f(n) ≤ kg(n)

b) ek1 > 0ek2 > 0en0 > n0: k1g(n) ≤ f(n) k2g(n)

c) ek > 0en0 Vn > n0: f(n) ≥ kg(n)

d) Vk > 0en0 Vn > n0: |(fn)| < kg(n)

1. f(n) e 0(g(n)) (average case) ->

2. f(n) e O(g(n)) (worse case) ->

3. f(n) e o(g(n)) (loose upper bound) ->

4. f(n) e N(g(n)) (best case) ->

1. B

2. A

3. D

4. C

Is SPACE(t(n)) ⊆ TIME(2^O(t(n)))?

a. This in yet unknown.

b. Yes, because a TM that uses t(n) tape cells cannot use more than 2^O(t(n)) time without repeating a configuration and thus looping and not halting

c. No, time and space complexity are unrelated

b. Yes, because a TM that uses t(n) tape cells cannot use more than 2^O(t(n)) time without repeating a configuration and thus looping and not halting

Decidability of languages does not depend on the model of computation.

a. This is an open problem

b. True

c. False

b. True

What are T-decidable close under?

Choose all that apply

A) union

B) complement

C)kleenex

D)intersection

A) union

B) complement

C)kleenex

D)intersection

What are T-recognizable close under?

Choose all that apply

A) union

B) complement

C)kleenex

D)intersection

A) union

C)kleenex

D)intersection

Which of the following is an application of the pumping lemma for regular languages?

A) Generating a regular expression for a given language.

B) Constructing a finite automaton for a given language.

C) Proving that a given language is not regular.

D) Finding the minimum number of states required for a given automaton.

C) Proving that a given language is not regular.

Translate the following NFA into a regular expression.

A) aa U (ab)

B) aa ∩ ab(ab)

C) aa(aa) U ab(ab)

D) aa U ab(ab)

E) a(aa) U ab(ab)

D) aa U ab(ab)

Which of the following is a property of a DFA?

A) It can accept e (the empty string).

B) It can have multiple start states.

C) It can have multiple transitions from a single state on the same input symbol.

D) It can recognize non-regular languages.

A) It can accept e (the empty string).

Which of the following is a difference between a DFA and an NFA (Select all that apply).

A) A DFA can accept e (the empty string), but an NFA cannot

B) A DFA can recognize non-regular languages, but an NFA cannot.

C) A DFA has one state transition for each input symbol, but an NFA can have zero or many transition per input symbol.

D) An NFA does allow e-transitions, a DFA does not.

C) A DFA has one state transition for each input symbol, but an NFA can have zero or many transition per input symbol.

D) An NFA does allow e-transitions, a DFA does not.

Which of the following is an advantage of using an NFA instead of a DFA?

A) There are no advantages to using an NFA over a DFA.

B) NFAs can recognize more languages than DFAs.

C) NFAs are simpler to combine (e.g. union, concatenation, Kleene-*) than DFAs.

D) NFAs have faster runtime than DFAs for the same language.

C) NFAs are simpler to combine (e.g. union, concatenation, Kleene-*) than DFAs.

What is a formal language?

A) A programming language with strict syntax rules.

B) A set of strings over a finite alphabet.

C) A method of communication used in formal settings.

D) A language with an infinite number of grammar rules.

E) A mathematical function that computes string values.

B) A set of strings over a finite alphabet.

Which of the following is a property of deterministic finite automata (DFA)?

A) It cannot perform e-transitions.

B) It allows for an infinite number of states.

C) Each state can have multiple transitions for the same input symbol.

A) It cannot perform e-transitions.

What characterizes a context-free grammar?

A) Production rules where each side can contain any string of terminals and non-terminals.

B) Grammar that can generate all possible strings over its alphabet.

C) Production rules with a single non-terminal on the left-hand side.

D) Grammar that requires context to interpret its strings.

E) Rules that allow for direct left recursion only.

C) Production rules with a single non-terminal on the left-hand side.

Which of the following languages is not recognized by a deterministic finite automaton?

A) {w | w contains an even number of 0s}

B) {w | w begins and ends with the same symbol}

C) {a^nb^n | n ≥ 0}

D) {a,b}*

E) The set of all strings over {0,1}, that do not contain the substring 00

C) {a^nb^n | n ≥ 0}

Which of the following best describes a pushdown automaton (PDA)?

A) A computational model that uses a stack to keep track of symbols

B) A machine capable of solving any computation problem

C) A finite automaton that has been extended with additional memory capacity

D) An automaton that can recognize any language in the Chomsky hierarchy

E) A deterministic machine used exclusively for parsing regular expressions

A) A computational model that uses a stack to keep track of symbols

What is the pumping lemma for regular languages used to prove?

A) That a given language is finite

B) That a given language is infinite but regular

C) That a given language is not regular

D) That all languages can be pumped

E) That a given language can be recognized by a Turing machine

C) That a given language is not regular

What is a Deterministic Finite Automaton (DFA) used for?

A) To recognize regular languages

B) To recognize context-free languages

C) To recognize context-sensitive languages

D) To recognize recursively enumerable languages

E) To recognize all languages

A) To recognize regular languages

Which of the following best describes a Non-deterministic Finite Automaton (NFA)?

A) An automaton where each input symbol uniquely determines the next state

B) An automaton where multiple transitions are possible from a single state for the same input symbol

C) An automaton that can recognize context-sensitive languages

D) An automaton that can recognize recursively enumerable languages

E) An automaton that can recognize context-free languages

B) An automaton where multiple transitions are possible from a single state for the same input symbol

What is the difference between DFAs and NFAs?

A) DFAs have more states than NFAs

B) NFAs can have multiple transitions for the same input symbols and states

C) DFAs can recognize context-free languages, while NFAs cannot

D) NFAs are always more powerful than DFAs

E) There is no difference between DFAs and NFAs

B) NFAs can have multiple transitions for the same input symbols and states

Which of the following classes of languages can be recognized by a pushdown automaton (PDA)? (Select all that apply.)

A) Regular languages

B) Context-free languages

C) Context-sensitive languages

D) Recursively enumerable languages

A) Regular languages

B) Context-free languages

What is the primary function of a context-free grammar (CFG)?

A) To define regular languages

B) To define context-sensitive languages

C) To define recursively enumerable languages

D) To generate strings in a context-free language

E) To recognize strings in a context-free language

D) To generate strings in a context-free language

Which of the following is a characteristic of a context-free languages?

A) They can be recognized by finite automata

B) They can be recognized by pushdown automata

C) They cannot be recognized by Turing machines

D) They can b generated by regular expressions

E) They cannot be recognized by context-sensitive grammars

B) They can be recognized by pushdown automata

What is the primary role of transitions in a finite automaton?

A) To define the states of the automaton

B) To define the movement between states based on input symbols

C) To define the start state of the automaton

D) To define the alphabet of the language

E) To define the acceptance criteria for the language

B) To define the movement between states based on input symbols

Which of the following statements is true about the Pumping Lemma

A) It can be used to prove that a language is regular.

B) It can be used to prove that a language is context-free.

C) It can be used to prove that a language is context-sensitive.

D) It can be used to prove that a language is recursively enumerable.

E) It can be used to prove that a language is not regular.

E) It can be used to prove that a language is not regular.

Which of the following is not a component of a pushdown automaton

A) Stack

B) Tape

C) State

D) Input alphabet

E) Transition function

B) Tape

What is the distinguishing feature of a regular language?

A) It can be recognized by a pushdown automaton

B) It can be generated by a context-free grammar

C) It can be recognized by a deterministic finite automaton

D) It can be recognized by a Turing machine

E) It can be generated by a non-deterministic automaton

C) It can be recognized by a deterministic finite automaton

Which of the following automata is the most powerful in terms of language recognition?

A) Generalized nondeterministic finite automaton

B) Pushdown automaton

C) Deterministic finite automaton

D) Non-deterministic finite automaton

E) None of the above

B) Pushdown automaton

What is the purpose of the transition function in a finite automaton?

A) To determine the start state of the automaton

B) To determine the alphabet of the language

C) To define the movement between states based on input symbols

D) To determine the acceptance criteria for the language

E) To define the final states of the automaton

C) To define the movement between states based on input symbols

Which of the following statements if false regarding the conversion of a NFA to a DFA

A) Every NFA has an equivalent DFA

B) Every DFA has an equivalent NFA

C) NFAs are more expressive than DFAs

D) NFAs can be converted to DFAs without any loss of expressive power

E) DFAs can be converted to NFAs without any loss of expressive power

C) NFAs are more expressive than DFAs

Which of the following languages is NOT context-free?

A) {a^nb^n | n ≥ 0}

B) {a^nb^mc^(n+m) | n,m ≥ 0}

C) {a^nb^nc^n | n ≥ 0}

D) {ww^R | W E {a,b}*}

E) {a^ib^jc^k | i != j V j != k}

C) {a^nb^nc^n | n ≥ 0}

In context-free grammars, what are terminals? (Select all that apply.)

A) Non-terminal symbols

B) Symbols that can be replaced by production rules

C) Symbols that cannot be replaced by production rules

D) Symbols from the output alphabet

E) Symbols from the stack alphabet

C) Symbols that cannot be replaced by production rules

D) Symbols from the output alphabet

Which of the following is not a valid context-free grammar?

A) S -> aS | Sb | e

B) S -> aS | bS | S

C) Sb -> aSbS | e

D) S -> aSb | bSa | e

E) S -> a | b

C) Sb -> aSbS | e

Which fo the following statements is true about regular expressions?

A) They can express any context-free language

B) They are more powerful than context-free grammars

C) They can express any regular language

D) they are less expressive than finite automata

E) They are equivalent to Turing machines

C) They can express any regular language

Which of the following is an example of a non-regular language?

A) {w | w contains an equal number of 0s and 1s}

B) {w | w contains an equal number of 0s}

C) {w | w starts and ends with the same symbol}

D) {w | w contains the substring 01}

E) {w | w does not contain the substring 01}

A) {w | w contains an equal number of 0s and 1s}