CODEWITHSUNDEEP
context-free-grammarpushdown-automatoncontext-free-language
Farzad
Farzad

Reputation: 1939

Pushdown Automata for an intersection?

I have a question about designing a pushdown automata for the language:

L = { w in {a, b}* : 2n_a(w) <= n_b(w) <= 3n_a(w) }

In other words, the number of b's in w is "between" 2 times the number of a's and three times the number of a's.

I'm confused about this question: I know (hopefully!) how to design the PDA to accept the language when the number of b's is equal to twice the number of a's or 3 times the number of a's separately.

This language seems to be an intersection of those, but I don't think there's a simple way to use the intersection to create a PDA. How can we incorporate the fact that the number can be between two values.

ANY help is much appreciated...

P.S. If you can also give the context-free grammar (and also explanation), it would be very very helpful also.

P.P.S: Also, if anyone can provide a link to somehow show how to construct context-free grammars step by step, I would really need it. (I found a link to regular grammars for regular expressions, but for context-free grammars, when I try to follow the variables and see that one variable goes to itself, or goes to another variable, which goes back to the initial variable, I REALLY get confused.)

Upvotes: 0

Views: 2168

Answers (1)

Addie
Addie

Reputation: 167

You need to make your PDA so that every a pushes two b's or three b's. For example, a String with 3 a's and 8 b's: first a pushes 3 b's, second a pushes 3 b's, third a pushes 2 b's.

I think this CFG covers all the cases: S -> aB|Ba|EOS B -> SbSbS|SbSbSbS

This means that for every a, there are two b's or three b's.

https://www.youtube.com/watch?v=AbbZVvQkees This is a great youtube channel for PDA's.

Upvotes: 0

Related Questions