Thread: Lanuage grammar help

  1. #1
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719

    Lanuage grammar help

    Ok, I'm having some trouble understanding language grammar. I've been trying to figure out these couple exercises, but I need some help.

    The first asks to find all possible strings of seven or fewer letters using this language:
    Code:
    <string>=$ | <word> | $<string>
    <word>=abb | a<word>bb
    Where | means "or".

    This is what I have so far:

    Code:
    $
    abb
    aabbbb
    $$
    $$$
    $$$$
    $$$$$
    $$$$$$
    $$$$$$$
    $abb
    $aabbbbb
    I feel like I'm missing something.

    The other was about writing recursive grammar for a language of strings of one or more letters. The first letter must be uppercase, and the other letters must be lowercase.

    Here is what I got:
    Code:
    <string>=<upper> | <string><lower>
    <upper>=A | B | ...Z
    <lower>=a | b | ...z
    Can someone confirm if I'm doing it right?

    Thanks a lot for any input!
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Both your answers look correct to me.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Can you not do $$abb (etc)?

  4. #4
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Quote Originally Posted by tabstop View Post
    Can you not do $$abb (etc)?
    To an extent, I believe... if I'm reading it right.

    According to the rules
    Code:
    <string>=$ | <word> | $<string>
    <word>=abb | a<word>bb
    <string> can equal <word> ("abb" or "aabbbb") and as such, according to the third conditional value of <string> can also equal $<word> (where <string> in the condition is substituted for it's second conditional value <word>),
    recursively to 7 letters. That would add the possibilities of:
    Code:
    * Text left hidden for OP, if he still wishes to figure them out
    $abb
    $$abb
    $$$abb
    $$$$abb
    $aabbbb
    Of course... it is 1AM.
    Last edited by SlyMaelstrom; 03-02-2009 at 12:04 AM.
    Sent from my iPadŽ

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    The valid forms of the first grammar are:
    "$" (from the '$' term of the <string> rule)
    any combination of n times 'a' followed by 2n times 'b', where n > 0 (the <word> rule and term)
    either of the above, prefixed by any number of '$' characters. (repeated application of the $<string> term)

    The second is correct.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Note that $aabbbbb has eight letters and hence doesn't belong to your list.

    The grammar above is a so-called context-free grammar, or Type-2 grammar in the Chomsky hierarchy. This hierarchy lets you easily determine what can be expressed in a certain grammar and how much effort is needed to decide whether a given word belongs to the corresponding language or not. My literature on this subject is in German, but I'm sure that there are plenty of books available in English as well.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by Snafuist View Post
    Note that $aabbbbb has eight letters and hence doesn't belong to your list.
    It's also not valid under the grammar. Looks like a typo.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. c++ grammar question
    By bpereira in forum C++ Programming
    Replies: 7
    Last Post: 09-29-2008, 08:22 AM
  2. strange grammar about volatile and operator overload
    By George2 in forum C++ Programming
    Replies: 6
    Last Post: 01-30-2008, 05:38 AM
  3. Programming an automata using context free grammar
    By louis_mine in forum C Programming
    Replies: 1
    Last Post: 06-14-2006, 03:37 PM
  4. Online Grammar...
    By Jaqui in forum A Brief History of Cprogramming.com
    Replies: 22
    Last Post: 05-26-2006, 01:59 AM
  5. Need algorithm for parser for Context-Free Grammar
    By Koedoe in forum C++ Programming
    Replies: 4
    Last Post: 04-07-2005, 01:31 AM