AMCAT Automata and Formal Languages 2

Question 1

Which of the following is the correct regular expression for the language of all binary strings containing at least one '1'?

Accepted Answer

(0|1)*1(0|1)*

Answer

0*10*

Answer

0*1(0|1)*

Answer

1(0|1)*

Question 2

An epsilon-NFA (NFA with epsilon transitions) is:

Accepted Answer

Equivalent in power to a standard NFA and DFA

Answer

More powerful than a standard NFA in terms of language recognition

Answer

More powerful than a DFA but less than a pushdown automaton

Answer

Capable of recognizing context-free languages

Question 3

Which of the following grammars is ambiguous?
A) S → aS | a
B) S → aSb | ab
C) S → SS | a
D) S → aSa | bSb | a | b

Accepted Answer

Grammar C

Answer

Grammar A

Answer

Grammar B

Answer

Grammar D

Question 4

What type of automaton is needed to recognize the language L = {ww^R | w is in {a,b}*}, where w^R is the reverse of w?

Accepted Answer

Non-deterministic Pushdown Automaton

Answer

Deterministic Finite Automaton

Answer

Deterministic Pushdown Automaton

Answer

Turing Machine

Question 5

The Myhill-Nerode theorem is used to:

Accepted Answer

Minimize a DFA by finding the minimum number of states

Answer

Convert an NFA to a DFA

Answer

Prove that a language is context-free

Answer

Generate regular expressions from grammars

Question 6

Which of the following operations on context-free languages does NOT always produce a context-free language?

Accepted Answer

Intersection of two context-free languages

Answer

Union of two context-free languages

Answer

Concatenation of two context-free languages

Answer

Kleene star of a context-free language