diff options
Diffstat (limited to 'usth/MATH2.3/5')
| -rw-r--r-- | usth/MATH2.3/5/README.md | 105 | ||||
| -rw-r--r-- | usth/MATH2.3/5/[Ch_Automata]_Practical.pdf | bin | 0 -> 30127 bytes | |||
| -rw-r--r-- | usth/MATH2.3/5/automata-to-grammar.c | 16 | ||||
| -rw-r--r-- | usth/MATH2.3/5/automata.c | 24 | ||||
| -rw-r--r-- | usth/MATH2.3/5/grammar-to-automata.cc | 29 | ||||
| -rw-r--r-- | usth/MATH2.3/5/nfa.cc | 45 | ||||
| -rw-r--r-- | usth/MATH2.3/5/turing.cc | 56 |
7 files changed, 275 insertions, 0 deletions
diff --git a/usth/MATH2.3/5/README.md b/usth/MATH2.3/5/README.md new file mode 100644 index 0000000..70e52fa --- /dev/null +++ b/usth/MATH2.3/5/README.md @@ -0,0 +1,105 @@ +# Computations +## Problem 1 +`automata.c`, e.g. + +### Input + 4 + 1 1 3 + 0 1 2 + 0 3 0 + 1 1 2 + 4 0011 + +### Output + yes + +## Problem 2 +`nfa.cc` takes a state table of a non-deterministic finite-state automaton, its +final states and a string from stdin and print either `yes` or `no` to stdout +to answer whether this string is recognized by the automaton, e.g. + +### Input + 12 + 0 0 0 + 0 0 1 + 0 1 3 + 1 0 0 + 1 1 1 + 1 1 3 + 2 1 0 + 2 1 2 + 3 0 0 + 3 0 1 + 3 0 2 + 3 1 1 + 2 + 2 3 + 101 + +### Output + yes + +## Problem 3 +`automata-to-grammar.c` + +### Input + 4 + 1 1 3 + 0 1 2 + 0 3 0 + 1 1 2 + +### Output + S -> $ + S -> 0T + S -> 1V + T -> 0T + T -> 1U + U -> 0V + U -> 1S + V -> $ + V -> 0T + V -> 1U + +## Problem 4 +`grammar-to-automata.cc` (C++17) + +### Input + 10 + S -> $ + S -> 0T + S -> 1V + T -> 0T + T -> 1U + U -> 0V + U -> 1S + V -> $ + V -> 0T + V -> 1U + +### Output + 4 + V T U 1 + U V S 0 + S T V 1 + T T U 0 + +## Problem 5 +`turing.cc` (C++17) takes a natural number `n` and `n` 5-tuples representing a +Turing machine (with `-1` being the blank), a natural number `m` and a string +of `m` binaries from stdin, then print the output string to stdout, e.g. + +### Input + 7 + 0 0 0 0 1 + 0 1 1 1 1 + 0 -1 3 -1 1 + 1 0 0 0 1 + 1 1 2 0 -1 + 1 -1 3 -1 1 + 2 1 3 0 1 + 6 + 0 1 0 1 1 0 + +### Output + 010000 diff --git a/usth/MATH2.3/5/[Ch_Automata]_Practical.pdf b/usth/MATH2.3/5/[Ch_Automata]_Practical.pdf new file mode 100644 index 0000000..47d14ce --- /dev/null +++ b/usth/MATH2.3/5/[Ch_Automata]_Practical.pdf Binary files differdiff --git a/usth/MATH2.3/5/automata-to-grammar.c b/usth/MATH2.3/5/automata-to-grammar.c new file mode 100644 index 0000000..430782a --- /dev/null +++ b/usth/MATH2.3/5/automata-to-grammar.c @@ -0,0 +1,16 @@ +#include <stdio.h> + +int main() +{ + int n, b, j, k; + + scanf("%d", &n); + for (int i = 0; i < n; ++i) { + scanf("%d %d %d", &b, &j, &k); + if (b) + printf("%c -> $\n", 'S' + i); + printf("%c -> 0%c\n%c -> 1%c\n", i+83, j+83, i+83, k+83); + } + + return 0; +} diff --git a/usth/MATH2.3/5/automata.c b/usth/MATH2.3/5/automata.c new file mode 100644 index 0000000..d18ca1e --- /dev/null +++ b/usth/MATH2.3/5/automata.c @@ -0,0 +1,24 @@ +#include <stdio.h> + +int main() { + int n; + scanf("%d", &n); + + int F[n], f[n][2]; + for (int i = 0; i < n; ++i) + scanf("%d %d %d", F + i, f[i], f[i] + 1); + + int m; + scanf("%d ", &m); + + char c[m + 1]; + scanf("%s", c); + + int state = 0; + for (int i = 0; i < m; ++i) + state = f[state][c[i] - 48]; + + puts(F[state] ? "yes" : "no"); + + return 0; +} diff --git a/usth/MATH2.3/5/grammar-to-automata.cc b/usth/MATH2.3/5/grammar-to-automata.cc new file mode 100644 index 0000000..125b3c9 --- /dev/null +++ b/usth/MATH2.3/5/grammar-to-automata.cc @@ -0,0 +1,29 @@ +#include <iostream> +#include <string> +#include <unordered_map> + +using namespace std; + +int +main () +{ + int n; + cin >> n; + + unordered_map<char, unordered_map<int, char>> automata; + unordered_map<char, int> finals; + for (int i = 0; i < n; ++i) + { + char c; + string s, t; + cin >> c >> t >> s; + if (s == "$") + finals[c] = 1; + else + automata[c][s[0] - '0'] = (s.length () == 1) ? '$' : s[1]; + } + + cout << automata.size () << endl; + for (auto& [c, m] : automata) + cout << c << '\t' << m[0] << '\t' << m[1] << '\t' << finals[c] << endl; +} diff --git a/usth/MATH2.3/5/nfa.cc b/usth/MATH2.3/5/nfa.cc new file mode 100644 index 0000000..8401202 --- /dev/null +++ b/usth/MATH2.3/5/nfa.cc @@ -0,0 +1,45 @@ +#include <iostream> +#include <string> +#include <unordered_map> +#include <vector> + +using namespace std; + +bool +recognize (unordered_map<int, unordered_map<int, vector<int>>>& f, + unordered_map<int, bool>& F, string& s, int i, int r) +{ + if (i >= s.size ()) + return F[r]; + for (auto const& t : f[r][s[i] - '0']) + if (recognize (f, F, s, i + 1, t)) + return true; + return false; +} + +int +main () +{ + int n; + unordered_map<int, unordered_map<int, vector<int>>> f; + cin >> n; + while (n--) + { + int s, i, r; + cin >> s >> i >> r; + f[s][i].push_back (r); + } + + unordered_map<int, bool> F; + cin >> n; + while (n--) + { + int s; + cin >> s; + F[s] = true; + } + + string s; + cin >> s; + cout << (recognize (f, F, s, 0, 0) ? "yes" : "no") << endl; +} diff --git a/usth/MATH2.3/5/turing.cc b/usth/MATH2.3/5/turing.cc new file mode 100644 index 0000000..7ef5deb --- /dev/null +++ b/usth/MATH2.3/5/turing.cc @@ -0,0 +1,56 @@ +#include <iostream> +#include <deque> +#include <tuple> +#include <unordered_map> + +using namespace std; + +int +main () +{ + int n; + unordered_map<int, unordered_map<int, tuple<int, int, int>>> tuples; + cin >> n; + while (n--) + { + int s, x, t, y, d; + cin >> s >> x >> t >> y >> d; + tuples[s][x] = {t, y, d}; + } + + deque<int> input; + cin >> n; + while (n--) + { + int i; + cin >> i; + input.push_back (i); + } + + int o {0}, i {0}, s {0}, x, d; + for (;;) + { + tie (s, x, d) = tuples[s][input[i - o]]; + if (!d) + break; + + if (i < o) + { + input.push_front (x); + o++; + } + else if (i - o == input.size ()) + input.push_back (x); + else + input[i - o] = x; + + if (d < 0) + i--; + else + i++; + } + + for (auto const& i : input) + cout << i; + cout << endl; +} |