Foundation of CS

NFA, DFA, regular expression question solving

HW 08-01 PDAs Push Down Automata
Problem 1
Figure 1 (above) shows a PDA in JFLAP with a single transition. Hand draw this PDA using the textbook
notation so I’m sure you can translate back and forth between book and JFLAP notation!
(Tip: I’m asking you to draw the picture below, but you have to fill in the 3 things indicated)
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 2
(converting between JFLAP and book notation for PDAs):
Figure 2 (above) shows a PDA in JFLAP with a single transition. Hand draw this PDA using the textbook
notation so I’m sure you can translate back and forth between book and JFLAP notation!
Problem 3
Figure 3 (above) shows a PDA in JFLAP with a single transition. Hand draw this PDA using the textbook notation so I’m
sure you can translate back and forth between book and JFLAP notation!
Problem 4
Figure 4 (above) shows a PDA in JFLAP with a single transition. Hand draw this PDA using the textbook notation.
HINT: be careful – Z in JFLAP means what in book notation??
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 5
Figure 5 (shown above) shows a PDA drawn in the style of the book with only a single transition. How would the
equivalent transition be labeled in JFLAP??
NOTE: All I want you to do is to tell me what gets filled in for thing1, thing2, and thing3 in the JFLAP image
below:
Problem 6
Figure 6 (shown above) shows a PDA drawn in the style of the book with only a single transition. How would the
equivalent transition be labeled in JFLAP??
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 7
Figure 7 (shown above) shows a PDA drawn in the style of the book with only a single transition. How would the
equivalent transition be labeled in JFLAP??
Problem 8
[Optional]
Find a context-free grammar for {anb2n | n ≥ 0} over the alphabet {a,b}
Problem 9
Use JFLAP to build a PDA for {anb2n | n ≥ 0} over the alphabet {a,b} Save as hw08_01_Problem9.jff
Problem 10
[optional] Find a context-free grammar for {anb2+n | n ≥ 0}over the alphabet {a,b}
Problem 11
JFLAP to build a PDA for {anb2+n | n ≥ 0}over the alphabet {a,b}
Save as hw08_01_Problem11.jff
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 12
[Optional]
Find a context-free grammar for the palindromes of even length over the alphabet {a,b}
Problem 13
[Optional]
Use JFLAP to build a PDA for the palindromes of even length over the alphabet {a,b}Save as hw08_01_Problem13.jff
Problem 14
Use JFLAP to build a PDA for the palindromes of odd length over the alphabet {a,b,c} Save as
hw08_01_problem14.jff
Problem 15
[Optional]
Find a context free grammar for the following language over the alphabet {a,b}:
{anbn+2 | n ≥ 0} ∪ {anb2n | n ≥ 0}
Hint: Use the technique for combining grammars under union that we learned. This should be really easy if you
did #1 and #3 already
Problem 16
Build a PDA for the following language over the alphabet {a,b}:
{anbn+2 | n ≥ 0} ∪ {anb2n | n ≥ 0}
hint: Use lambda jumps as a sort of a trick like the trick you used in the previous problem for grammars, e.g.,
here’s an outline:
Save as hw08_01_problem16.jff
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 17
Use set notation to describe the language recognized by the PDA shown in Figure 8 above
Problem 18
[optional]Give a CFG for the language recognized by the PDA shown in Figure 8 above.
Problem 19
Is the PDA shown in figure 8 deterministic? Why or why not?
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 20
The PDA shown in figure 9 (below) recognizes a regular language. Give a regular expression for the language recognized
by the PDA shown in figure 9
Problem 21
The PDA shown in figure 9 recognizes a regular language. Give an NFA for the language recognized by the PDA shown in
figure 9 (Just hand draw this – not JFLAP)
Problem 22
Is figure 9 a Deterministic or Nondeterminisitic PDA? Why?
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 23
Let L be the language generated by the PDA shown in figure 10 below
i.
ii.
iii.
iv.
v.
vi.
vii.
viii.
Is Λ in L?
Is ab in L?
Is abc in L?
Is abcd in L?
Is aabcd in L?
Is abcdd in L?
Is aabbccd in L?
Is abbccdd in L?
Describe L in English in a way that someone who understands the definitions of the words “set,” “string,” and
“language” as we use them in class, but otherwise does not know anything about the material we’ve learned in
class. (Tip: the idea behind this question is that before I get you to represent L as a grammar or using set
notation I get you to demonstrate that you understand what L represents. So convince me that you do!)
Problem 24
Use set notation to describe the language of the PDA shown in figure 10 above
Problem 25
[optional]
Is the language of the PDA shown in figure 10 regular? If so, give a regular expression for this language, if not, give a
CFG for it.
Problem 26
Is the PDA shown in figure 10 a Deterministic PDA or a Nondeterministic PDA? Why?
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 27
[Optional]
Create a PDA in JFLAP that accepts the language {anbcn | n >= 1}
(important – note the range of values for n!!
Save as hw08_01_problem27.jff
Problem 28
Create a PDA in JFLAP that accepts the language abncd2enfg
Save as hw08_01_problem28.jff
Problem 29
n n*2
[optional]Create a PDA in JFLAP that accepts the language a b
Save as hw08_01_problem29.jff
Problem 30
Create a PDA in JFLAP that accepts the language
anb(n*2)+5
Save as hw08_01_problem30.jff
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 31
[optional]
Find a context-free grammar for the language over the alphabet {a,b} that consists of all strings with the same number of
a’s and b’s. *** NOTE that the a’s and b’s can come in any order. All of the following strings are in that language:
● ab
● ba
● aaabbabbbbaaba
● bbbaaaab
● Λ
Problem 32
[optional]
● Use JFLAP to build a PDA for the language over the alphabet {a,b} that consists of all strings with the same
number of a’s and b’s. *** NOTE that the a’s and b’s can come in any order. Save as hw08_01_problem32.jff
Hint 1: Use the stack to keep track of whichever letter you have more of
● Hint 2: Below and on the next page are a few snapshots I took of some “fast run” runs I did for my PDA on
different strings in jflap. (I’ve hidden the state number so I don’t give too much away, but I’m hoping they’ll help.)
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 33
[optional]
Find a context free grammar for a*b
Problem 34
Build a PDA in JFLAP for a*b (hint – since it’s a regular language, if you want you can build it with what the book would
call “nops” but we do it a little differently in JFLAP.
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42027130
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.