CODEWITHSUNDEEP
regexbnf
Matt P
Matt P

Reputation:

BNF to regular Expressions

How can I describe the language

A → AA | ( A ) | ε

generates using regular expressions?

Upvotes: 2

Views: 2806

Answers (5)

Martin Brown
Martin Brown

Reputation: 25320

As others have said you cannot do this with a single regular expression, however you can tokenize it with two "\(" and "\)". Seeing that your language can only have brackets in it though I'm not sure this is going to be very useful.

Note: You will also need a passer to ensure the brackets are paired up correctly. So “(()()” will tokenize but will not parse.

Upvotes: 0

Boris
Boris

Reputation:

I'm not sure about how you could notate that language, but that language isn't regular, as can be shown using the pumping lemma for regular languages (and thus, it can't be noted by a regex). An intuitive explanation is that accepting words from that language would require the FDA to 'remember' the number of opening parenthesis that it just read every time it begins to read closing parenthesis, and that isn't possible for them as they have no 'memory'. A push-down automaton, on the other hand...

Could that language be noted as {(n)n}*, for any n?

Upvotes: 1

HenryR
HenryR

Reputation: 8519

You can't - regular expressions can only recognise a small subset of possible languages. In particular, informally, any language that requires an unbounded amount of memory potentially to recognise is not RE recognisable.

Here, you'd need an unbounded amount of memory to remember how many opening parentheses you've seen in order to make sure the number of closing parentheses are the same.

You'll need some mechanism that is capable of parsing Context-Free Grammars to be able to recognise languages described by BNF in general. Modern parsers are very good at this!

Upvotes: 0

MSalters
MSalters

Reputation: 179917

Regular expressions accept strings from regular languages. Regular languages can also be accepted by an FSM.

There's an potentially infinite number of brackets in your language that you have to match up. That means you need an infinite state, obviously impossible in any Finite State Machine. Therefore, your language isn't regular and can't be matched with a regex.

Upvotes: 14

David Schmitt
David Schmitt

Reputation: 59346

Regular expressions cannot match nesting brackets.

Upvotes: 6

Related Questions