Chomsky and CFL

When trying to transform a regular expression into a FSA, the first step is to…

• write down the vocabulary of strings that are matched.

• draw as many states as you can in one minute.

• cry.

• simplify the regex.

Answer explanation

If a language is empty, its corresponding FSA…

• does not exist.

• has no accepting state.

• is non-deterministic.

Answer explanation

The language being empty means that there is not a single string that can be accepted. This means that we cannot have an accepting state.

The intersection between two languages denotes…

• a single word that exists in both of them.

• the set of items that are accepted in one of the languages but not the other.

• the set of items that are accepted in both languages.

• the set of items that are accepted in at least one of the two languages.

The corresponding minimal FSA for the regular expression (a|b)[ab]*[cd]*d?c? can be drawn with … states.

• 3

• 1

• 4

• 2

Answer explanation

(a|b)[ab]*[cd]*d?c? can be simplified to [ab]+[cd]*

It becomes clear that two states are enough.

DFA are not allowed to have…

• epsilon edges.

• a final state.

• multiple transition options for a given input.

• more than a certain number of edges going out of a state.

Answer explanation

[ab]+[cd]*

Context-free languages are also called […] in the Chomsky Hierarchy.

• Type-0

• Type-1

• Type-2

• Type-3

Regular languages are […] than context-free languages.

• more expressive

• less expressive

When it comes to natural languages, CFG can be used for…

• syntax parsing.

• tokenising.

• recognising e-mail addresses.

• semantic parsing.

What is one of the big advantages of context-free languages over regular ones?

• they are computationally less expensive

• their corresponding automata are simpler than FSA

• they can 'remember' how often a symbol occurs and make sure another symbol occurs equally as often

• they are less complicated to describe.

Regular languages are to FSA as context-free languages are to…