Could someone help me with this formal language?

Asked

Viewed 218 times

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.

computer-theory

2 answers

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.

3

The following grammar is enough to recognize this language:

Gramática que obriga n <= m <= 2n

This grammar generates words incrementally, always increasing a a and one or two bs 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:

autômato de pilha

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.