8
Could someone help me with the following language:
{a^n b^m | n<= m <= 2n}
Forgive my ignorance, but I’m failing to form a battery automaton with this language. I’m trying through a deterministic stack automaton but nothing comes out.
8
Could someone help me with the following language:
{a^n b^m | n<= m <= 2n}
Forgive my ignorance, but I’m failing to form a battery automaton with this language. I’m trying through a deterministic stack automaton but nothing comes out.
7
{a^n b^m | n<= m <= 2n}
that is to say:
Accepted expression with N elements and A and M elements of B, M between N and 2N.
In practice, the automaton accepts:
AB
ABB
AABB
AABBB
AABBBB
...
That is, the amount of B
must be equal to the quantity of A
, or greater than the amount of A
, as long as it’s not more than twice A
.
EDIT
I thought this site was cool to help you.
I get it, now I just have to create a stack automaton for this and that’s what I’m not getting, thanks man!
Don’t forget to stroll through the Tour. You’re welcome!
3
The following grammar is enough to recognize this language:
This grammar generates words incrementally, always increasing a a
and one or two b
s in a self-nested way.
This grammar is a context-free grammar, generated from that meta-language: /a/215974/64969
The stack automaton is this:
I created a self-answered question to deal precisely with the transformation from context-free grammars to stack automata. I even used the grammar of this question as an example
Browser other questions tagged computer-theory
You are not signed in. Login or sign up in order to post.
What language are we talking about?
– Leonel Sanches da Silva
formal language
– Breno Lima