Homework SourseWe discussed in class how a pushdown automaton with two stac
We discussed in class how a pushdown automaton with two stacks would be able to accept strings in the non-context-free language AnBnCn (“n a’s followed by n b’s followed by n c’s”).
Algorithm Sketch: read a’s and push them onto stack1, while reading b’s pop stack1 for each b and push one b onto stack2; while reading c’s, pop stack2; the string is accepted when the string is completely read and stack1 and stack2 are empty, otherwise, the string is not in AnBnCn. (Work out the finer points by thinking through the various scenarios of mismatched numbers of a’s, b’s , and c’s, and unacceptable permutations of these symbols. This will help prevent undesirable run-time behaviors/crashes of your program , e.g., attempts to pop an empty stack.)
In a programming language of your choice (likely C++, possibly Python, or Java, or … ), write a simple program that reads a string of characters in {a,b,c} , once from left to right, and uses two stacks in order to determine whether or not the input string is a member in AnBnCn.
Note: You are not asked to write a program that “simulates” the process of a formal PDA as we have studied. I.e., your program will not read next state/stack configurations off a transition table. Instead, freely write a program to accomplish the task in the manner by which a student would so fresh out of basic CSE.
In order to qualify for extra credit, your program must fulfill the following requirements:
• It must correctly identify membership or non-membership for all 64+4 sample inputs listed below.
• It must do so without any counting of frequencies for symbols ‘a’, ‘b’, and ‘c’.
• It must use two stacks (either use an explicit stack data structure or use another suitable data structure in stack fashion.)
• It must have been designed and implemented by yourself, individually, not as a team.
• Your program must feature a Boolean function which determines for a given string whether or not it is in AnBnCn. (No “big main()” without functions!).
Instead of typing in all 64+4 inputs by hand, you may want to consider generating them are as part of your program. Let the below lines in Python suggest a manner by which to automatically produce the inputs. Python users are free to use this code as is. Users of C++ or other may treat it as pseudo-code.
asubs = [\"\", \"aaa\", \"aaaaaa\", \"aaaaaaaaa\"]
bsubs = [\"\", \"bbb\", \"bbbbbb\", \"bbbbbbbbb\"]
csubs = [\"\", \"ccc\", \"cccccc\", \"ccccccccc\"]
all_abc = []
for a in asubs:
for b in bsubs:
for c in csubs:
all_abc.append(a+b+c)
# generate three random permutations of a’s,b’s, and c’s
# or hardcode your own;
random.seed()
for i in range(4):
rstr = list(random.choice(all_abc))
random.shuffle(rstr)
rstr = \'\'.join(rstr)
all_abc.append(rstr)
The list of sample inputs to test for membership in AnBnCn. Some are, many are not in the language. (What about item 1.?)
1.
2. ccc
3. cccccc
4. ccccccccc
5. bbb
6. bbbccc
7. bbbcccccc
8. bbbccccccccc
9. bbbbbb
10. bbbbbbccc
11. bbbbbbcccccc
12. bbbbbbccccccccc
13. bbbbbbbbb
14. bbbbbbbbbccc
15. bbbbbbbbbcccccc
16. bbbbbbbbbccccccccc
17. aaa
18. aaaccc
19. aaacccccc
20. aaaccccccccc
21. aaabbb
22. aaabbbccc
23. aaabbbcccccc
24. aaabbbccccccccc
25. aaabbbbbb
26. aaabbbbbbccc
27. aaabbbbbbcccccc
28. aaabbbbbbccccccccc
29. aaabbbbbbbbb
30. aaabbbbbbbbbccc
31. aaabbbbbbbbbcccccc
32. aaabbbbbbbbbccccccccc
33. aaaaaa
34. aaaaaaccc
35. aaaaaacccccc
36. aaaaaaccccccccc
37. aaaaaabbb
38. aaaaaabbbccc
39. aaaaaabbbcccccc
40. aaaaaabbbccccccccc
41. aaaaaabbbbbb
42. aaaaaabbbbbbccc
43. aaaaaabbbbbbcccccc
44. aaaaaabbbbbbccccccccc
45. aaaaaabbbbbbbbb
46. aaaaaabbbbbbbbbccc
47. aaaaaabbbbbbbbbcccccc
48. aaaaaabbbbbbbbbccccccccc
49. aaaaaaaaa
50. aaaaaaaaaccc
51. aaaaaaaaacccccc
52. aaaaaaaaaccccccccc
53. aaaaaaaaabbb
54. aaaaaaaaabbbccc
55. aaaaaaaaabbbcccccc
56. aaaaaaaaabbbccccccccc
57. aaaaaaaaabbbbbb
58. aaaaaaaaabbbbbbccc
59. aaaaaaaaabbbbbbcccccc
60. aaaaaaaaabbbbbbccccccccc
61. aaaaaaaaabbbbbbbbb
62. aaaaaaaaabbbbbbbbbccc
63. aaaaaaaaabbbbbbbbbcccccc
64. aaaaaaaaabbbbbbbbbccccccccc
65. cbbbbbbcbcccbcb
66. ccbcbabbcbacccbabaacbabc
67. aacacaacabcabacacb
68. aaaccaaca
Solution
PROGRAM CODE:
package parser;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class PushDownAutomata {
ArrayList<String> stringList = new ArrayList<String>();
Stack<Character> stack1 = new Stack<Character>();
Stack<Character> stack2 = new Stack<Character>();
public void readFile()
{
Scanner scanner;
try {
scanner = new Scanner(new File(\"strings.txt\"));
while(scanner.hasNext())
{
String[] value = scanner.nextLine().split(\" \");
//System.out.println(value[1]);
if(value.length>1)
{
stringList.add(value[1]);
//System.out.println(\"Reading: \" + value[1]);
}
}
scanner.close();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public void checkStrings()
{
for(int i=0; i<stringList.size(); i++)
{
String value = stringList.get(i);
//boolean isAvailable = false;
//boolean isBAvailable = false;
int counter = 0;
int lengthofString = value.length();
if(value.contains(\"a\") && value.contains(\"b\") && value.contains(\"c\"))
{
while(lengthofString != counter && value.charAt(counter) == \'a\')
{
stack1.push(\'a\');
counter++;
}
if(stack1.isEmpty())
{
stringList.set(i, \"Wrong\");
}else
{
while(lengthofString != counter && value.charAt(counter) == \'b\')
{
stack2.push(\'b\');
if(!stack1.isEmpty())
stack1.pop();
else
{
stringList.set(i, \"Wrong\");
break;
}
counter++;
}
if(stack2.isEmpty())
{
stringList.set(i, \"Wrong\");
}
else
{
while(lengthofString != counter && value.charAt(counter) == \'c\')
{
if(!stack2.isEmpty())
stack2.pop();
else
{
stringList.set(i, \"Wrong\");
break;
}
counter++;
}
}
}
if(!stack1.isEmpty() || !stack2.isEmpty())
stringList.set(i, \"Wrong\");
}
else
{
stringList.set(i, \"Wrong\");
}
}
}
public void printCorrectStrings()
{
for(int i=0; i<stringList.size(); i++)
{
if(!stringList.get(i).equals(\"Wrong\"))
System.out.println(stringList.get(i));
}
}
}
package parser;
public class Driver {
public static void main(String [] args)
{
PushDownAutomata automata = new PushDownAutomata();
automata.readFile();
//automata.printCorrectStrings();
automata.checkStrings();
automata.printCorrectStrings();
}
}
input:
1.
2. ccc
3. cccccc
4. ccccccccc
5. bbb
6. bbbccc
7. bbbcccccc
8. bbbccccccccc
9. bbbbbb
10. bbbbbbccc
11. bbbbbbcccccc
12. bbbbbbccccccccc
13. bbbbbbbbb
14. bbbbbbbbbccc
15. bbbbbbbbbcccccc
16. bbbbbbbbbccccccccc
17. aaa
18. aaaccc
19. aaacccccc
20. aaaccccccccc
21. aaabbb
22. aaabbbccc
23. aaabbbcccccc
24. aaabbbccccccccc
25. aaabbbbbb
26. aaabbbbbbccc
27. aaabbbbbbcccccc
28. aaabbbbbbccccccccc
29. aaabbbbbbbbb
30. aaabbbbbbbbbccc
31. aaabbbbbbbbbcccccc
32. aaabbbbbbbbbccccccccc
33. aaaaaa
34. aaaaaaccc
35. aaaaaacccccc
36. aaaaaaccccccccc
37. aaaaaabbb
38. aaaaaabbbccc
39. aaaaaabbbcccccc
40. aaaaaabbbccccccccc
41. aaaaaabbbbbb
42. aaaaaabbbbbbccc
43. aaaaaabbbbbbcccccc
44. aaaaaabbbbbbccccccccc
45. aaaaaabbbbbbbbb
46. aaaaaabbbbbbbbbccc
47. aaaaaabbbbbbbbbcccccc
48. aaaaaabbbbbbbbbccccccccc
49. aaaaaaaaa
50. aaaaaaaaaccc
51. aaaaaaaaacccccc
52. aaaaaaaaaccccccccc
53. aaaaaaaaabbb
54. aaaaaaaaabbbccc
55. aaaaaaaaabbbcccccc
56. aaaaaaaaabbbccccccccc
57. aaaaaaaaabbbbbb
58. aaaaaaaaabbbbbbccc
59. aaaaaaaaabbbbbbcccccc
60. aaaaaaaaabbbbbbccccccccc
61. aaaaaaaaabbbbbbbbb
62. aaaaaaaaabbbbbbbbbccc
63. aaaaaaaaabbbbbbbbbcccccc
64. aaaaaaaaabbbbbbbbbccccccccc
65. cbbbbbbcbcccbcb
66. ccbcbabbcbacccbabaacbabc
67. aacacaacabcabacacb
68. aaaccaaca
OUTPUT:
aaabbbccc
