Home > Archive > Prolog > May 2007 > Grammar
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| ccanderson18@hotmail.com 2007-05-02, 10:03 pm |
| Consider the following grammar:
<S> -> <A> a <B> b
<A> -> <A> b I b
<B> -> a <B> I a
Which of the following sentences are in the language generated by this
grammar?
a. baab
b. bbbab
c. bbaaaaa
d. bbaab
Can anyone help me on this?
| |
|
| On 2 May 2007 18:17:43 -0700, ccanderson18@hotmail.com wrote:
>Consider the following grammar:
>
><S> -> <A> a <B> b
>
><A> -> <A> b I b
>
><B> -> a <B> I a
>
>Which of the following sentences are in the language generated by this
>grammar?
>
>a. baab
>
>b. bbbab
>
>c. bbaaaaa
>
>d. bbaab
>
>Can anyone help me on this?
No. This is not free tutoring service
A.L.
| |
| Chaerephon 2007-05-03, 4:04 am |
| Ο <ccanderson18@hotmail.com> _γραψε στο μήνυμα
news:1178155063.217165.39640@h2g2000hsg.googlegroups.com...
> Consider the following grammar:
>
> <S> -> <A> a <B> b
>
> <A> -> <A> b I b
>
> <B> -> a <B> I a
>
> Which of the following sentences are in the language generated by this
> grammar?
>
> a. baab
>
> b. bbbab
>
> c. bbaaaaa
>
> d. bbaab
>
> Can anyone help me on this?
>
C'est justement _ ça que sert Prolog ... !!!
--
Avec mes meilleures salutations.
Chaerephon
| |
| Jussi Piitulainen 2007-05-03, 4:04 am |
| ccanderson18@hotmail.com writes:
> Consider the following grammar:
>
> <S> -> <A> a <B> b
> <A> -> <A> b I b
> <B> -> a <B> I a
....
> Can anyone help me on this?
The problem is the left recursion in the second nonterminal. An
easy workaround is to add a depth counter to all productions,
like so:
sentence([_|T]) --> ananas(T), [a], banana(T), [b].
ananas([_|T]) --> ananas(T), [b] | [b].
banana([_|T]) --> [a], banana(T) | [a].
This can be used to test or generate all sentences of at most
the given depth, assuming you can convince yourself that the
translation is correct and work out how to use it.
| |
| Carlo Capelli 2007-05-03, 10:02 pm |
| I think you should try to solve the problem without Prolog, or you will run
into some technical problem (left recursive rules),
that probably you will be required to apprentice later in the course.
Given the simplicity of the grammar, it's apparent this is a test on your
understanding of production rules...
Think to the non terminals A and B. You should see that A can only produce a
sequence of 1 or more b.
B is similar. From this you should see the sequences proposed that can be
discarded...
Bye Carlo
<ccanderson18@hotmail.com> ha scritto nel messaggio
news:1178155063.217165.39640@h2g2000hsg.googlegroups.com...
> Consider the following grammar:
>
> <S> -> <A> a <B> b
>
> <A> -> <A> b I b
>
> <B> -> a <B> I a
>
> Which of the following sentences are in the language generated by this
> grammar?
>
> a. baab
>
> b. bbbab
>
> c. bbaaaaa
>
> d. bbaab
>
> Can anyone help me on this?
>
|
|
|
|
|