nbansal90 / DFA-NFA Public

Notifications You must be signed in to change notification settings
Fork 0
Star 0

Count Strings Problem: Hacker Rank

0 stars 0 forks Branches Tags Activity

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 6 Commits
README.md		README.md
d_seperation.cpp		d_seperation.cpp
nfa_parsing_dfa.cpp		nfa_parsing_dfa.cpp
ways_count.cpp		ways_count.cpp

Repository files navigation

DFA-NFA

Count Strings Problem: Hacker Rank

Given a regular expression and an integer, , count how many strings of length are recognized by it.

Sources Used for reference: https://www.cs.york.ac.uk/fp/lsa/lectures/REToC.pdf https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Powerset_construction And a bit of insipiration from: https://github.com/kennyledet/Algorithm-Implementations/blob/master/Thompsons_Construction_Algorithm/C%2B%2B/AlexMathew/RE_to_NFA.cpp

Steps:

Parsing ---> converting Infix regex to Postfix
Postfix Expression---> NFA (Thompson Algorithm)
NFA --> DFA (Subset Construction Algorithm)

4)DFA-->Adjacency MAtrix

About

Count Strings Problem: Hacker Rank

Report repository

Releases

No releases published

Packages

No packages published

Languages

C++ 100.0%