CODEWITHSUNDEEP
computation-theory
A_Pumpkin
A_Pumpkin

Reputation: 51

NPDA for L= {w ∈ {a,b}*: number of a's is twice the number of b's}

I have been trying to find a NPDA for this language but I can't come up with anything that will accept all of the words in the language. I did try making its accepting condition an empty stack and using the stack alphabet {$ a b} but maybe I should try something else?

Upvotes: -1

Views: 4762

Answers (3)

valxyz
valxyz

Reputation: 1

Given the language:

$$L = {x \in {a, b}^* \mid n_a(x) = 2 \cdot n_b(x)}$$

Where the number of 'a's is exactly twice the number of 'b's.

Base cases

  • Strings like {aab, baa, aba} are valid.

Grammar

S → λ
S → aab
S → Saab
S → aSab
S → aaSb
S → aabS
S → baa
S → Sbaa
S → bSaa
S → baSa
S → baaS
S → aba
S → Saba
S → aSba
S → abSa
S → abaS

Expected strings

The grammar should generate strings like the following:

  • baabaa
  • baaaab
  • abbaaa
  • aabbaa
  • bbaaaa
  • aaaabb
  • aabaab
  • aaabab
  • abaaabbaa
  • baaababaa
  • aababbaaaaab
  • ...

Testing with JFLAP

After defining this grammar, you can test it using tools like JFLAP to verify the generated strings. By default, JFLAP generates different combinations of the grammar rules until a match is found. If the string doesn't belong to the language, JFLAP may calculate millions of combinations. In my case, I allowed it to compute up to 15 million combinations before canceling the execution to test the next string.

JFLAP simulation grammar

Upvotes: 0

Durga Harika Challa
Durga Harika Challa

Reputation: 24

The context free grammer for number of a's is twice the number of b's is:

S--> aaSb / €(epsilon)

Push down automata can be done for a^2nb^n.push down automata is nothing but the finite automata with memory (can be stack).

  • Here, for every two a's push one 'a' into the stack and for the input symbol 'b' pop 'a' from the stack.

  • At the end, if the stack is empty then the string is accepted.

PDA image for a^2nb^n:

PDA image for a^2nb^n

δ(q0,a,z0)=(q0,az0)
δ(q0,a,a)=(q1,a)
δ(q1,a,a)=(q0,aa)
δ(q1,b,a)=(q2,ϵ)
δ(q2,b,a)=(q2,ϵ)
δ(q2,ϵ,z0)=(q3,z0)

where,

  • Q={q0,q1,q2,q3}
  • Σ=(a,b)
  • q0=initial state
  • q3=final state

From the figure for the odd number of a's push into the stack and for even a's skip.Then for each 'b' pop one 'a' from the stack. At the end, an empty stack represents that the string is accepted.

Upvotes: 0

Traian GEICU
Traian GEICU

Reputation: 1786

Maybe you are looking the equivalent Grammar for the given Regular Expression.
If so maybe this one with the following productions:

S->AAb | SAAb | ASAb | AASb | AAbS
A->a

Some Tests:

aab : S->AAb->aAb->aab
aaaabb : S-> AASb -> AA(AAb)b -> aaaabb

Could check also with other example and see if fit on all cases.

If fine always should have on
Result = (2*count_of_b) for a, count_b

Looking twice, A->a can be removed and have only:

S->aab|Saab|aSab|aaSb|aabS

Test:

aaaabb : aaSb(S_4)->aaaabb(S_1), etc.

Upvotes: 1

Related Questions