Check AB in a string

Question

Given a string S, made up of only 'a's and 'b's. Check the string for the following rules. Program in python using recursion.

1. The string begins with an 'a'
2. Each 'a' is followed by nothing or an 'a' or "bb"
3. Each "bb" is followed by nothing or an 'a'

I've tried the following code.

def checkAB(s):
    if len(s) == 0:
        return 1
    if s[0] == 'a':
        if s[1] == 'a' or s[1] == 'b':
            return checkAB(s[2:])
        if s[1] == None:
            return 1
        else:
            return 0
    elif s[0] == 'b':
        if s[1] == 'b' and s[2] == None:
            return checkAB(s[2:])
        elif s[1] == 'b' and s[2] == 'a':
            return 1
        else:
            return 0

s = input()
if s[0] == 'a':
    if checkAB(s[1:]):
        print('true')
    else:
        print('false')
else:
    print('false')

But it shows string index out of range error.

Thanks in advance!

Answer 1

Fortunately, the rules can be phrased as a regular expression:

1. start with "a": ^a
2. continue with an arbitrary amount of "a" or "bba": (a|bba)*
3. finish at any point or with just "bb": (bb$)?

combined regex: ^a(a|bba)*(bb$)?

(you can probably simplify the regex a bit more, not sure though)

In Python:

import re

def check_rules(s: str) -> bool:
    return bool(re.fullmatch(r"^a(a|bba)*(bb$)?", s))

Some tests:

def test_positive():
    assert check_rules("abba")
    assert check_rules("abbabb")
    assert check_rules("aaabbaabb")
    assert check_rules("abbabbabbaaa")


def test_negative():
    assert not check_rules("aba")
    assert not check_rules("baba")
    assert not check_rules("baabb")
    assert not check_rules("aabbbaa")

cheers

edit: about program in python using recursion - you should always use the right technique for the right job and a recursive function is not useful in this case, because Python has a limit for recursion depth which you may reach pretty fast if you try to analyze a few million characters. A regular expression is an efficient way to analyze a regular language and technically it uses recursion right here (a|bba)* ;)