Question

Construct a deterministic PDA for L = {w ∈ {a, b}* : na (w) = nb...

Construct a deterministic PDA for L = {w ∈ {a, b}* : na (w) = nb (w)}

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Here we have 2 different paths to final state q3 since the starting symbol can be either a or b. Path from q0-q1-q3 is when starting symbol is a and path from q0-q2-q3 is when starting symbol is b.

In the q0-q1-q3 path, push all a's onto stack. And pop an 'a' when b occurs.

a, z|a -> Push a onto stack when stack is empty.

a, a|aa -> Push a onto stack when top element of stack is a.

Finally €, z|z means when we have reached to end of symbol and stack is empty, then go to state q3 which is final state. String which lead to state q3 are the string which are accepted by PDA

If you have any questions comment down. Please just don't simply downvote and leave. If you are satisfied with answer , please? upvote.. I really need it, thanks

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Find a regular expression for the following language L= {w∈{a,b}*:(na(w)-nb(w)mod)3=1} please show explanation and steps
Find a regular expression for the following language L= {w∈{a,b}*:(na(w)-nb(w)mod)3=1} please show explanation and steps
Question 2 a) Construct a Pushdown Automaton (PDA) for the language L (M) = {a, b}*...
Question 2 a) Construct a Pushdown Automaton (PDA) for the language L (M) = {a, b}* where, if there are any a’s must precede all b's and the number of b's must be equal to or twice the number of a’s. a) Trace the computations for the strings aabb, bbb, and abb in the PDA obtained in Question 2
PDA for L = {a^i b^j | i<j} PDA for L = {a^i b^j | i>j}
PDA for L = {a^i b^j | i<j} PDA for L = {a^i b^j | i>j}
Construct an NFA for the following language: L = {w ∈ {a,b}∗ : every a is...
Construct an NFA for the following language: L = {w ∈ {a,b}∗ : every a is immediately followed by at most 2 b's}
Consider the language L = { w w : w ∈ { 0 , 1 }...
Consider the language L = { w w : w ∈ { 0 , 1 } ∗ } is not context-free. Note that this is the language of all strings that consist of some combination of 0s and 1s, followed immediately by that same combination of 0s and 1s. For example, 0101, 101101, and 110110 are all in the language because they consist of a string followed by itself. Can you build a PDA to recognize this language? (Hint: you...
Consider the language L3 over alphabet Σ = { a, b }, L3 = { w...
Consider the language L3 over alphabet Σ = { a, b }, L3 = { w ∈ Σ* | w is a palindrome of any length}. Construct a PDA that recognizes L3. Implement that PDA in JFLAP
Use CFG or PDA to prove L= {0a1b0c : b ≠ a + c; a, b,...
Use CFG or PDA to prove L= {0a1b0c : b ≠ a + c; a, b, c ≥ _0} is a context-free language. Please add your explanation, thank you. If you can use the theorem(union of CFL and regular language = CFL) is also welcomed.
Let two Einstein solids be in thermal contact with NA = NB = 2. Assume that...
Let two Einstein solids be in thermal contact with NA = NB = 2. Assume that the resulting system is isolated and that it contains 9 units of energy (that is, UA + UB = 9ε). (a) Construct a table with UA, UB, ΩA, ΩB, and ΩAB for all possible macropartitions of the system. (b) Calculate the probabilities of each of the possible macropartitions. (c) Identify the most likely macropartitions.
PDA for {a^i b^j i != j} PDA for {a^i b^j c^k, i = j or...
PDA for {a^i b^j i != j} PDA for {a^i b^j c^k, i = j or j = k} PDA for # of a's = # of b's PDA for # b's = twice # of a's
1. If L={a^nb^n: n>=0} then what is the CFG of L* ?
1. If L={a^nb^n: n>=0} then what is the CFG of L* ?
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT