Results 1 to 5 of 5

Math Help - context-free grammar

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    3

    context-free grammar

    Hi,
    I need some help with this.
    Can you explain me the part 'Identifying useless variables' at the page 8 on some simple example?
    Thank you.

    silapo.72@gmail.com

    I need to explain how to use alogorithm pre* at grammar reduction. Can you explain me it on some example please?

    The problem is described in link down:
    http://www7.in.tum.de/um/bibdb/esparza/ufpcfg.pdf

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    I need to explain how to use alogorithm pre* at grammar reduction. Can you explain me it on some example please?
    pre* is not an algorithm, but an operator that maps a language into a language. The description of how the operator actually works depends on how the input and output languages are represented. The article assumes that they are represented by finite automata, so it gives an algorithm that takes an automaton accepting the input language and produces an automaton accepting the output language.

    So, do you need an explanation how the automata-converting algorithm works or how it is used for the task of finding useless variables? For the second, consider the following grammar.

    S -> AB
    A -> a | aA
    B -> BA

    Here B is useless because it is not productive, i.e., it is not the case that B\stackrel{*}{\Rightarrow} w for some w\in T^*=\{a\}^*. To come to this conclusion using the suggested method, we start with an automaton M1 that accepts all of \{a\}^*. It consists of one accepting state with a loop labeled by a. The algorithm described in the article transforms this automaton into an M2 such that M2 accepts u\in\{S,A,B,a\}^* iff u\stackrel{*}{\Rightarrow}w for some w\in\{a\}^*. Then we check whether M2 accepts B (it should not).

    The variable A is productive; however, it is also useless because it is not reachable, i.e., it is not the case that S\stackrel{*}{\Rightarrow}w_1Aw_2 for some w_1,w_2\in\{a\}^*. This is because every string obtained from S (the article calls them sentential forms) has a B in it. To come to this conclusion, we start with an automaton N1 that accepts the language a^*Aa^*. (To be precise, this is a regular expression that describes the language.) The algorithm converts it into an N2 that accepts u\in\{S,A,B,a\}^* iff u\stackrel{*}{\Rightarrow}w for some w\in a^*Aa^*. Then we check whether N2 accepts S (it should not).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2011
    Posts
    3
    Thanks for replie.
    You asked me, what I need to explain, so I need an explanation how it is used for the task of finding useless variables on some simple example.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    Did the info above answer your question?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2011
    Posts
    3
    Original question was answered. Thanks.
    But I want ask you new question.
    Down on the picture is automaton M1 you described, is it OK?

    Can you please draw automaton M2 and N2? Thank you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof Please: Context Free Grammar
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2011, 07:10 PM
  2. Context free grammar question.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 25th 2011, 04:09 PM
  3. Context-free grammar
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: June 29th 2010, 09:41 AM
  4. context-free language and grammar
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 28th 2010, 04:42 PM
  5. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2010, 09:26 PM

Search Tags


/mathhelpforum @mathhelpforum