Could anyone help me with this formal language?

Navigation
8

Could someone help me with the following language: 

{a^n b^m | n<= m <= 2n}

Sorry for ignorance, but I can not form a stack automaton with this language. I'm trying through a deterministic stack automaton but nothing comes out.

    
asked by anonymous 30.05.2017 / 00:12

2 answers

7

{a^n b^m | n<= m <= 2n} means:

  

Expression is accepted with N elements and A and M elements of B, where M is 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 amount of A , or greater than the amount of A , as long as it is not greater than double A .

EDIT

I found this site cool to help you.

    
30.05.2017 / 00:39
2

The following grammar is enough to recognize this language:

Thisgrammargenerateswordsincrementally,alwaysincreasingaandoneortwobsinauto-nestedmode.

Thisgrammarisa context-free grammar generated from this meta-language: link

The stack automaton is this:

I've created a self-addressed question to deal fairly with transforming context-free grammars into stack automata. I have even used the grammar of this question as an example

    
28.09.2017 / 03:55
What is the correct use of the "in" operator, in javascript? Customize the browser message to a "required"