Can any one help with this ? Not sure how to do it
For an alphabet: $A = \{a, b, c, d\}$
For each of the words $abc$, $cbc$, $ac$, $cca$, and $bbba$, determine whether the word matches each of the following regular expressions:
- $(a\lor b\lor c)b^*(a\lor c)$
- $c^*ab$
- $c(a\lor b\lor c)^*$
I’ll do the first regular expression with each of the five words as an example of what you’re to do, and I’ll leave the other two regular expressions to you.
When does a word $w$ over the alphabet $A$ match the regular expression $(a\lor b\lor c)b^*(a\lor c)$?
The first letter of $w$ must match the expression $a\lor b\lor c$, which simply means that it must be $a,b$ or $c$; it cannot be $d$. All five of the words $abc,cbc,ac,cca$, and $bbba$ begin with $a,b$, or $c$, so none of them is ruled out at this stage.
The last letter of $w$ must match the expression $a\lor c$, so $w$ must end in $a$ or $c$. All five of the words $abc,cbc,ac,cca$, and $bbba$ end in $a$ or $c$, so none of them is ruled out at this stage.
What’s left of $w$ after we remove the first letter (which is matched up with $a\lor b\lor c$ and the last letter (which is matched up with $a\lor c$) must match the middle part of the regular expression, $b^*$. In other words, it must be a string of $0$ or more $b$s. As the table below clearly shows, this is true for each of our five words except $cca$. Thus, we can match each of the words $abc,cbc,ac$, and $bbba$ with this regular expression, but we cannot do so with $cca$.
$$\begin{array}{c|c|c} w&\text{first letter}&\text{last letter}&\text{remainder}\\ \hline abc&a&c&b\\ cbc&c&c&b\\ ac&a&c&\\ cca&c&a&\color{red}c\\ bbba&b&a&bb \end{array}$$