This package refers to the topic of automata theory, which includes DFA, NDFA, Mealy machines, Moore machines, Finite state machine and Turing machine.
Project description
For more information, see the GitHub Repository.
AutomaPy
The package contains a set of tools and algorithms for theoretical computer science, which could include automata theory as well as other topics.
Installation
pip install AutomaPy
Examples of How To Use (AutomaPy)
1. Create a program that implements a machine that accepts strings ending with '101'.
from AutomaPy import DFA
dfa = DFA()
dfa.addState("A" , {"0": "A", "1":"B"}, initial_state = True)
dfa.addState("B" , {"0": "C", "1":"B"})
dfa.addState("C" , {"0": "A", "1":"D"})
dfa.addState("D" , {"0": "C", "1":"B"}, final_state=True)
print(dfa.endingWithOneZeroOne("101"))
print(dfa.endingWithOneZeroOne("01101"))
print(dfa.endingWithOneZeroOne("011011"))
The code creates a DFA
object and defines four states: A
, B
, C
, and D
. The transitions between these states are defined by dictionaries that map input symbols (0 or 1) to the next state. The initial state is set to A
, and the final state is set to D
.
The code then uses the endingWithOneZeroOne()
method of the DFA object to check if the given strings end with the pattern "101"
. This method takes a string as input and returns True
if the DFA accepts the string (i.e., if it ends in the final state), and False
otherwise.
The first call to endingWithOneZeroOne()
with the input string "101"
returns True
because the DFA transitions from state A
to state B
on the first "1"
, then from state B
to state C on the "0"
, and finally from state C
to state D
on the "1", which is the final state.
The second call to endingWithOneZeroOne()
with the input string "01101"
also returns True
because the DFA follows the same transitions as in the first case, but with an additional "0"
input that takes it from state A
to state C
.
The third call to endingWithOneZeroOne()
with the input string "011011"
returns False because the DFA transitions from state A
to state C
on the first "0"
, then from state C
to state A
on the second "1"
, and finally from state A to state B
on the third "1"
, which is not the final state.
2. Design a Program for creating machine that accepts three consecutive one.
from AutomaPy import DFA
dfa = DFA()
dfa.addState("A" , {"0": "A", "1":"B"}, initial_state = True)
dfa.addState("B" , {"0": "A", "1":"C"})
dfa.addState("C" , {"0": "A", "1":"D"})
dfa.addState("D" , {"0": "F", "1":"E"}, final_state=True)
dfa.addState("E" , {"0": "E", "1":"E"})
dfa.addState("F", {"0": "F", "1":"G"}, final_state=True)
dfa.addState("G", {"0": "F", "1":"H"}, final_state=True)
dfa.addState("H", {"0": "F", "1":"D"}, final_state=True)
print(dfa.threeConsecutiveOne("010111"))
print(dfa.threeConsecutiveOne("01011"))
print(dfa.threeConsecutiveOne("010101"))
The code creates a DFA object and defines eight states: A
, B
, C
, D
, E
, F
, G
, and H
. The transitions between these states are defined by dictionaries that map input symbols (0 or 1) to the next state. The initial state is set to A
, and the final states are set to D
, F
, G
, and H
.
The code then uses the threeConsecutiveOne()
method of the DFA object to check if the given strings contain three consecutive ones. This method takes a string as input and returns True
if the DFA accepts the string (i.e., if it ends in one of the final states), and False
otherwise.
The first call to threeConsecutiveOne()
with the input string "010111"
returns True
because the DFA transitions from state A
to state B
on the first "0"
, then from state B
to state C
on the first "1"
, then from state C
to state D
on the second "1"
, and finally to one of the final states (F, G, or H)
on the third "1"
.
The second call to threeConsecutiveOne()
with the input string "01011"
returns False
because the DFA
transitions from state A
to state B
on the first "0"
, then from state B
to state C
on the first "1"
, then from state C
to state D
on the second "1"
, but it does not reach a final state because there is no third "1"
.
The third call to threeConsecutiveOne()
with the input string "010101"
returns False
because the DFA transitions from state A
to state B
on the first "0"
, then from state B
to state A
on the first "1"
, then from state A
to state B
on the second "0"
, then from state B
to state A
on the second "1"
, and finally from state A
to state B
on the third "0"
, which is not a valid transition according to the DFA definition.
3. Write a program for tokenization of given input.
from AutomaPy import DFA
dfa = DFA()
print(dfa.tokenize("This is an example of tokenization."))
The tokenize()
method of the DFA object is then used to tokenize
a given string. This method takes a string as input and returns a list of tokens, where each token is a tuple that contains the token type and the token value.
In the given code, the tokenize
method is called with the input string "This is an example of tokenization."
. The method uses the predefined rules to split the input string into tokens
, which are returned as a list of tuples. Each tuple contains a token type and the corresponding token value. For example, the first tuple in the list might be ('WORD', 'This'
), indicating that the token is a word and its value is "This"
.
4. Design a program for accepting decimal number divisible by 2.
from AutomaPy import DFA
dfa = DFA()
dfa.addState("A", {"0": "A", "1": "B"}, initial_state=True, final_state=True)
dfa.addState("B", {"0": "A", "1": "B"})
print(dfa.decimalNumberDivisibleByTwo("10")) # Decimal number of "10" is 2
print(dfa.decimalNumberDivisibleByTwo("110")) # Decimal number of "10" is 6
print(dfa.decimalNumberDivisibleByTwo("101")) # Decimal number of "10" is 5
The code creates a DFA that recognizes decimal numbers divisible by 2 using the AutomaPy package. The DFA has two states ("A" and "B")
and transitions based on input symbols "0"
and "1"
. The decimalNumberDivisibleByTwo()
method simulates the DFA on a decimal number represented as a string and returns True
if the DFA reaches a final state after consuming the entire string, indicating that the number is divisible by 2. The method is called with three different input strings and returns True
for the first two and False
for the last one, based on whether the input string represents a decimal number that is divisible by 2 or not.
5. Design a program for creating a machine which accepts string having equal no. of 1’s and 0’s.
from AutomaPy import DFA
dfa = DFA()
dfa.addState("A", {"0": "B", "1": "B"}, initial_state=True, final_state=True)
dfa.addState("B", {"0": "A", "1": "A"})
print(dfa.equalNumberOfOneZero("10"))
print(dfa.equalNumberOfOneZero("101100"))
print(dfa.equalNumberOfOneZero("1011"))
The code creates a DFA that recognizes strings containing an equal number of 1s
and 0s
using the AutomaPy package. The DFA has two states ("A" and "B")
and transitions based on input symbols "0"
and "1"
. The equalNumberOfOneZero()
method simulates the DFA on an input string and returns True
if the DFA reaches a final state after consuming the entire string, indicating that the string has an equal number of 1s
and 0s
. The method is called with three different input strings and returns True
for the first and last one and False
for the second one, based on whether the input string has an equal number of 1s
and 0s
or not.
6. Design a program for creating a machine which count number of 1's and 0's in a given string.
from AutomaPy import DFA
dfa = DFA()
dfa.addState("A", {"0": "A", "1": "A"}, initial_state=True)
print(dfa.countNumberOfOneZero("0101"))
print(dfa.countNumberOfOneZero("01"))
print(dfa.countNumberOfOneZero("011111"))
print(dfa.countNumberOfOneZero("00000"))
The countNumberOfOneZero()
method in the code counts the number of occurrences of "0"
and "1"
symbols in the input string and returns the count as a string.
For example, if the input string is "0101"
, the method will return "The number of 0's is 2 and the number of 1's is 2"
. Similarly, if the input string is "011111"
, the method will return "The number of 0's is 1 and the number of 1's is 5"
.
7. Design a program for Turing machine that’s accepts the even number of 1's.
from AutomaPy import TuringMachine
tm = TuringMachine()
tm.addState('A', {'0': ('A', '0', 'R'), '1': ('B', '0', 'R'), '_': ('B', '_', 'L')}, initial_state=True, final_state=True)
tm.addState('B', {'0': ('B', '0', 'R'), '1': ('A', '0', 'R'), '_': ('A', '_', 'L')})
print(tm.turingMachineEvenOnes("")) # True (because 0 is even number)
print(tm.turingMachineEvenOnes("1")) # False
print(tm.turingMachineEvenOnes("1111")) # True
The turingMachineEvenOnes()
method checks whether a binary input string has an even number of 1's
using the Turing machine defined in the example.
It returns a boolean indicating whether the input string is accepted by the Turing machine, which is True
if the string has an even number of 1's
and False
otherwise.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file AutomaPy-1.2.6.tar.gz
.
File metadata
- Download URL: AutomaPy-1.2.6.tar.gz
- Upload date:
- Size: 7.6 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.2 CPython/3.11.0
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 26819b993d213b6ad0541d863016a08100267cbd9d8ce477a238ceeca49feec0 |
|
MD5 | 5ab84595b5426c7397c4079246cf6617 |
|
BLAKE2b-256 | c6897bc3f2430970079fbb2b3bd1feacfc6bba17fc95dfda287bdbacfc07aa30 |
File details
Details for the file AutomaPy-1.2.6-py3-none-any.whl
.
File metadata
- Download URL: AutomaPy-1.2.6-py3-none-any.whl
- Upload date:
- Size: 9.1 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.2 CPython/3.11.0
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7fcf58818bf93ab57e95a945fadf44f6105eca108e73a0e699a4557db83eaa4d |
|
MD5 | f6331bf18d0db50f56249746754caa5f |
|
BLAKE2b-256 | a449ea0a509aab35475289cb4287a0cbcf64b54cd54c09a0f9f8d22f9ce5b1a6 |