Regular expression with quantity dependence

Question

Is it possible to create regular expression that will describe words like:

aabc
aaaabcbc
aaaaaabcbcbc

?

Words are created like each occurrence of (bc) on the right is connected with occurrence (aa) on the left.

Words below are not valid:

aa
bc
aaabc
aaaabc
aabcbc

Kamehameha · Accepted Answer · 2014-02-04T15:10:24.657

2

No it cannot be expressed in terms of regular expressions. That is because, your expression, requires a number of "aa" followed by equal number of "bc". This requires infinite memory. FA do not have infinite memory.

It can be expressed in context-free grammar.-

S -> aaSbc | έ     Epsilon stands for string of zero length(empty string).

This generates strings like - Valid string - έ(Empty string), aabc, aaaabcbc and so on.

Read more about context free and regular grammar here.

edited Feb 04 '14 at 15:10

answered Feb 04 '14 at 12:27

Kamehameha

5,423
1
23
28

Correct *`'This requires memory. Regular grammars do not have memory.'`* to `'This requires unbounded(infinite) memory, and FA contains only finite memory in-terms of states'`. – Grijesh Chauhan Feb 04 '14 at 14:39
Not regular grammar but FA, grammar doesn't require memory. read [Finiteness of Regular Language](http://stackoverflow.com/questions/20803894/finiteness-of-regular-language/20818068#20818068) – Grijesh Chauhan Feb 04 '14 at 14:56

score 0 · Answer 2 · 2014-02-04T15:05:57.677

0

Just fyi it would be possible in non regular languages.

For example you could play with balancing groups in .NET and get something like this:

^(?<a>aa)+(bc(?<-a>))+(?(a)(?!))$

edited Feb 04 '14 at 15:05

answered Feb 04 '14 at 14:59

yes, but it's a programming language feature and not theoretical approach. – Conrad Feb 04 '14 at 15:31
1

@Conrad Although regex != regular expression but mistake is your tags @ user3271881 just a regex. – Grijesh Chauhan Feb 04 '14 at 17:13

Regular expression with quantity dependence

2 Answers2