CODEWITHSUNDEEP
regexregular-languageformal-languages
user814447
user814447

Reputation:

find a regular expression for strings containing the substring aba over the alphabet {a, b}? (formal language theory)

The questions asks to find a regular expression for strings containing the substring aba over the alphabet {a, b}.

Does this mean anything can precede/procede aba so that the regular expression would be:

(aUb)*(aba)*(aUb)*

or is the question simply looking for:

(aba)*

Note: U means union and * means 0 or more times.

Upvotes: 2

Views: 3407

Answers (3)

Ramon Snir
Ramon Snir

Reputation: 7560

Since * means 0 or more, ε is in the first language, while you do not want it (it doesn't contain aba). You are looking for (aUb)*aba(aUb)*.

Upvotes: 4

jacobm
jacobm

Reputation: 14035

The former: any string that contains aba at least once.

Upvotes: 0

K-ballo
K-ballo

Reputation: 81349

A substring is defined as

noun

a string that is part of a longer string

Also note that the second expression is a subset of the first.

Upvotes: 0

Related Questions