Regular languages: Practice Questions

Which of the following describes a regular language based on the formal definitions in the syllabus?

Consider the set difference operation. Given the sets \(A = \{x | x \in \mathbb{N} \wedge x < 5\}\) and \(B = \{2, 4, 6\}\), what is the result of the operation \(A \setminus B\)?

Which regular expression correctly represents the language over the alphabet \( \{a, b\} \) that accepts strings containing at least one 'a' followed by zero or more 'b's, where the entire sequence can then be repeated any number of times?

Which regular expression metacharacter is used to signify zero or more repetitions of the preceding element?

Consider a Finite State Machine designed to accept any string that ends with the suffix "101" over the alphabet \(\{0, 1\}\). Which regular expression correctly defines the same language?

Which specific regular expression metacharacter is used to indicate that the preceding element must appear one or more times?

A Deterministic Finite Automaton (DFA) is constructed to recognize the language defined by the regular expression \( (0|1)*1 \). Describe the final state of this machine after processing the input string "1010" and explain if it is an accepting state.

Given the set \( S = \{0, 1\} \), calculate the cardinality of the Cartesian product \( S \times S \times S \) and list the resulting elements.

A language is considered regular if it can be represented by a regular expression or accepted by a Finite State Machine (FSM). Consider the alphabet \( \Sigma = \{0, 1\} \).

(a) Write a regular expression for a language that accepts all strings where every '0' is immediately followed by at least two '1's. Strings may also consist of '1's only or be the empty string.

(b) Draw the state transition table for a Deterministic Finite Automaton (DFA) that recognizes the language described in part (a). Clearly label your states, the start state, and the accepting state(s).

(c) A student claims that the set \( L = \{0^n 1^n | n \ge 1\} \) is a regular language because it can be described using the compact notation shown in set theory. Explain, with reference to the properties of regular languages and FSMs, why this claim is incorrect.

(d) Simplify the regular expression \( (1|0|1)^* \) and describe the language it represents in plain English.

A regular language is defineable by a regular expression or a finite state machine. Consider the alphabet \( \Sigma = \{a, b\} \).

(a) Construct a regular expression that defines all strings which contain at least one 'a' and end with exactly two 'b's.

(b) Explain the difference between a subset and a proper subset in the context of the set of all strings in this language compared to the set of all strings over the alphabet \( \Sigma \).

(c) Calculate the cardinality of the set of strings in this language that have a length of exactly 4.