Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2017-12-09 09:40:47

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 156
Website

write a regular expression with just two a's each word?

write a regular expression with just two a's each word?

is following answer true?

ans : (aa + b*)

I teacher answer was " b*ab*ab*

is the first answer true too?


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

#2 2017-12-09 21:12:06

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,202

Re: write a regular expression with just two a's each word?

hi Hannibal lecter

I think it is true.  But say more about what led up to the question. 

What is the mathematical topic ?

Do you have a definition for an 'expression' ?

Does aa mean 'a AND a' ?

Does a + b mean 'a OR b ?

Does a* mean 'NOT a' ?

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#3 2017-12-30 11:47:19

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 156
Website

Re: write a regular expression with just two a's each word?

yes it's mean a or b

aa + b* and it's wrong for { babab, bbabbabb,bbbabbbbabbbb,....}

because the expretion of aa + b*  is = { aa , b , aab,baa,...}


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

#4 2017-12-30 21:36:27

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,202

Re: write a regular expression with just two a's each word?

hi Hannibal lecter

Sorry; I don't think I've understood this question at all.

aa + b*  is = { aa , b , aab,baa,...}

I'm interpreting aa + b* as meaning "a AND a OR NOT b

aa "a AND a"
b
aab "a AND a AND b"
etc.
and {...} as meaning "the set containing ...

How are these equal?

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#5 2017-12-31 08:24:31

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,154
Website

Re: write a regular expression with just two a's each word?

Hi bob,

Hannibal Lecter is referring to regular expressions in formal language theory.

"a" denotes the set containing the character a, i.e. a = {a}.

"ε" denotes the set containing the empty string (which has zero length).

"∅" as usual denotes the empty set.

All characters belong to some alphabet A, from which one can derive sentences. For instance, a string of parentheses like '))(((' is a sentence formed from the alphabet {(, )}. Some sentences will be true with respect to one language, but false with respect to others. For example, you might like to write some sentence which claims that every element of a set is either even or odd. That sentence would be true in
, but not in
, for instance (because we can't establish an order on
without introducing a norm, e.g. absolute value). This might seem trivial, but it allows us to distinguish between different structures (in this case, that
and
are different groups). These two groups are clearly not isomorphic, but we can apply the same principle to prove that two groups might not be. The nice thing about this is that this can work with lots of types of structures, even graphs.

The * notation refers to the Kleene star, which can either operate on sets of strings, or sets of characters. If S is some set of strings derived from some alphabet A, then S* is the smallest superset containing ε which is also closed under concatenation. In other words, S* has to contain all possible concatenations of whichever strings it contains, e.g. {ab, c}* = {ε, ab, c, abab, abc, ...}. I'm sure there's some kind of rule dictating which elements are listed first. Unless the set of characters is trivial (i.e. empty set or ε) then the Kleene star applied to S will give us an infinite set (which is always countable). So in this case, b* = {ε, b, bb, bbb, bbbb, ...}.

Another example: ab* = {a, ab, abb, abbb, abbbb, ...}

+ means 'choose either/or'. For example, "a + b" means "choose either a or b". So (a+b)* means "choose either a or b, then take all possible concatenations". In other words, (a+b)* is the set of all possible words you can make from {a,b}.

So aa + b* = {aa, b, aab, baa, bb, aabb, bbaa, bbb, ...}

Hannibal Lecter is asking for the sentence which generates all words containing exactly two instances of the character 'a', which is "b*ab*ab*".

aa + b* does not generate a set containing only characters with exactly two instances of the letter 'a', because it contains the elements b, bb, bbb, bbbb, ... all of which don't have any 'a' in them.

In general, the regular expression b*ab*ab*a...b*ab* (where 'a' appears n times) generates all words which contain the letter 'a' exactly n times.

Infinite strings are a different story.

Online

#6 2017-12-31 22:01:53

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,202

Re: write a regular expression with just two a's each word?

hi zetafunc,

Thanks for the explanation.  Now the question and answer are both clear to me.  smile

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

Board footer

Powered by FluxBB