Results 1 to 3 of 3

Math Help - Is that an adequate description of a language described by a grammar?

  1. #1
    Member alexgeek's Avatar
    Joined
    Mar 2010
    From
    Wales, UK
    Posts
    77

    Question Is that an adequate description of a language described by a grammar?

    Given the following grammar I have been asked to describe the language it generates:
     S \rightarrow aT
    T \rightarrow a \,|\, UTV
    U \rightarrow ab \,|\, ba
    V \rightarrow ac \,|\, ca

    I started with some examples:
    S \implies aT \implies aa
    S \implies aT \implies aUTV \implies abTac \implies abaac
    S \implies aT \implies aUTV \implies baTca \implies baUTVca \implies baabaacca

    So my description is:
    A language where b's and c's are balanced (including zero of each) centred around an a, such that there will always be 1 more a than the number of b's or the number of c's.

    The exact question is "What language is generated by the grammar?", given this information would you agree that this is an adequate answer?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,667
    Thanks
    606

    Re: Is that an adequate description of a language described by a grammar?

    Hey alexgeek.

    I don't know what is expected by your professors/lecture-persons/tutors but when I think of a language I think of the syntactic properties associated with the language whether that includes some sort of grammar, finite automata description, or markov model (or a combination of the three).

    It's just a little hard to know exactly what the question is asking let alone to give an adequate answer.

    Do you have another question like this that has an existing solution? Also are doing this as part of a particular course? (Compiler design, linguistics, etc)?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Is that an adequate description of a language described by a grammar?

    Quote Originally Posted by alexgeek View Post
    So my description is:
    A language where b's and c's are balanced (including zero of each) centred around an a, such that there will always be 1 more a than the number of b's or the number of c's.
    First, this is a description of words that result from T, not S. S adds an additional a in the beginning. Second, this description is true for all words in the language of T, but it is also true of some words outside the language. Namely, it does not preclude words where c occurs in the first half or where 3 b's occur in a row.

    I would describe this language as a(ab|ba)^na(ac|ca)^n.

    It is recommended to post questions about formal languages in the Discrete Math subforum.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 8th 2011, 01:37 PM
  2. Are these adequate estimators?
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: July 16th 2010, 05:06 PM
  3. context-free language and grammar
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 28th 2010, 04:42 PM
  4. Regular Grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 20th 2010, 08:58 AM
  5. Forming a language with Regular Grammar
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 26th 2010, 12:54 AM

Search Tags


/mathhelpforum @mathhelpforum