I am finishing up the Intro to Computer Science 101 course at Udacity and am looking for some help addressing one of the final quiz problems. The following code returned a "pass" when submitted but I feel like I am not getting at the heart of the challenge in this quiz. Any help or suggestions about how to approach and think about the problem would be appreciated.
The problem:
"""
Define a Python procedure, in_language(<string>),
that takes as input a string and returns True
if the input string is in the language described by the BNF grammar below
(starting from S) and returns False otherwise.
BNF grammar description:
S => 0 S 1
S => 1 S 0
S => 0
"""
# Tests. These all should print True if your procedure is defined correctly
print in_language("00011") == True
print in_language("0") == True
print in_language("01") == False
print in_language("011") == False
print in_language("01002") == False
Here's my code so far:
def in_language(bnf):
if len(bnf) % 2 == 0:
return False
if any(i in '23456789' for i in bnf) == True:
return False
if bnf[len(bnf)/2] != '0':
return False
else:
return True
This code will return True for submissions not of the given Backus-Naur Form:
S => 0 S 1
S => 1 S 0
S => 0
such as '11111011111'
print in_language('11111011111') == False
I am still wrapping my head around recursion, but it seems like there is a way to address this problem recursively? Either that or my next step would have been to check the first and last characters of the string to see if they were exclusively a zero and a one (not both), then remove them and continue pruning the string until I got to the base case, or, "middle" zero. I was surprised that the code passed the quiz at this point.
Of note, my thinking about the code:
if len(bnf) % 2 == 0:
The first if conditional occurred to me because given the B-N form, any iteration will result in an odd number of numbers, so string length divisibility by 2 indicates something not of that form.
if any(i in '23456789' for i in bnf) == True:
The second "if" was also a simply consideration because the problem is only looking for strings constructed of ones and zeros (I suppose I could have included the alphabet as well, or simply written if any(i not in '01' for i in bnf) .
if bnf[len(bnf)/2] != '0':
The third "if" is similarly looking for a qualifying feature of the given B-N form - no matter what the expression according to the given syntax, there will be a zero in the middle - and making use of Pythons floor division as well as the index start at zero.
Any thoughts or suggestions of alternative solutions would be greatly appreciated, thanks!
As I am new to StackOverflow, I did research this question before posting. Any posting style considerations (too verbose?) or concerns would also be helpful :)
Okay,
I took duskwoof's suggestion and came up with this:
def in_language(bnf):
# corresponding to: S => 0 S 1
if bnf[0] == '0' and bnf[-1] == '1':
return in_language(bnf[1:-1])
# corresponding to: S => 0 S 1
if bnf[0] == '1' and bnf[-1] == '0':
return in_language(bnf[1:-1])
# corresponding to: S => 0
if bnf == '0':
return True
return False
and it works for cases which follow the form, but python barfs when I submit cases which do not... and I still feel like there is something I am missing about recursion and parsing the strings for Backus-Naur Forms. How should I think about handling the cases which don't follow the form? Thank you for the help. I'll keep wrestling with this.
This seems to work better - passes all the test cases:
def in_language(bnf):
if len(bnf) > 2:
# corresponding to: S => 0 S 1
if bnf[0] == '0' and bnf[-1] == '1':
return in_language(bnf[1:-1])
# corresponding to: S => 0 S 1
if bnf[0] == '1' and bnf[-1] == '0':
return in_language(bnf[1:-1])
# corresponding to: S => 0
if bnf == '0':
return True
return False
but again, I'm totally a newB @programming, so any advice or input would be very helpful... I still don't feel like I have a very general solution; just something specific to this particular BNF grammar.
I am still wrapping my head around recursion, but it seems like there is a way to address this problem recursively?
This is precisely how you are expected to approach this problem. Don't try to overthink the problem by analyzing what properties the strings in this language will have (e.g, length modulo 2, what characters it will contain, etc)! While this could potentially work for this specific language, it won't work in general; some languages will simply be too complicated to write an iterative solution like you're describing.
Your solution should be a direct translation of the description of the language -- you shouldn't have to think too much about what the rules mean! -- and should use recursion for rules which have S on the right side. It should be written in the form:
def in_language(bnf):
if ...: # corresponding to: S => 0 S 1
return True
if ...: # corresponding to: S => 1 S 0
return True
if ...: # corresponding to: S => 0
return True
return False
(The solution you currently have is a "false solution" -- it will pass the tests given in the problem, but will fail on certain other inputs. For example, the string 000 is not in this language, but your function will say it is.)