What language is accepted by the npda in Example 7.4 if we use F = {q0 , qf }? Not sure if answer is L = {a + b}^n; n>=
Posted: Sat Nov 27, 2021 2:36 pm
What language is accepted by the npda in Example 7.4 if we use F
= {q0 , qf }?
Not sure if answer is L = {a + b}^n; n>= 0} or L = ((ab)*; n
>=0}. Both could be wrong.
EXAMPLE 7.4 Construct an npda for the language L = {w € {a,b}* : na (w) = nb (w)}. = = As in Example 7.2, the solution to this problem involves counting the number of a's and b’s, which is easily done with a stack. Here we need not even worry about the order of the a's and b’s. We can insert a counter symbol, say 0, into the stack whenever an a is read, then pop one counter symbol from the stack when a b is found. The only difficulty with this is that if there is a prefix of w with more b’s than a's, we will not find a 0 to use. But this is easy to fix; we can use a negative counter symbol, say 1, for counting the b’s that are to be matched against a's later. The complete solution is given in the transition graph in Figure 7.3. a, 0,00; b, 1, 11 a, z, Oz; b, 0, 2; b, z, 1z, a, 1, 2, 90 9f λ, Z, 7 FIGURE 7.3 In processing the string baab, the npda makes the moves E (20, baab, z) F (qo, aab, 1z) + (90, ab, z) + (90,6,0z) F (20, 1, z) F (qf, , z) and hence the string is accepted.
= {q0 , qf }?
- What Language Is Accepted By The Npda In Example 7 4 If We Use F Q0 Qf Not Sure If Answer Is L A B N N 1 (244.36 KiB) Viewed 72 times
>=0}. Both could be wrong.
EXAMPLE 7.4 Construct an npda for the language L = {w € {a,b}* : na (w) = nb (w)}. = = As in Example 7.2, the solution to this problem involves counting the number of a's and b’s, which is easily done with a stack. Here we need not even worry about the order of the a's and b’s. We can insert a counter symbol, say 0, into the stack whenever an a is read, then pop one counter symbol from the stack when a b is found. The only difficulty with this is that if there is a prefix of w with more b’s than a's, we will not find a 0 to use. But this is easy to fix; we can use a negative counter symbol, say 1, for counting the b’s that are to be matched against a's later. The complete solution is given in the transition graph in Figure 7.3. a, 0,00; b, 1, 11 a, z, Oz; b, 0, 2; b, z, 1z, a, 1, 2, 90 9f λ, Z, 7 FIGURE 7.3 In processing the string baab, the npda makes the moves E (20, baab, z) F (qo, aab, 1z) + (90, ab, z) + (90,6,0z) F (20, 1, z) F (qf, , z) and hence the string is accepted.