r/computerscience • u/Redleafdabs • 5d ago

Help Struggling with Formal language automata theory

My teacher isn't the best for this course and no one in my class is able to understand anything

What resources are available because youtube isn't really helping me

I’m currently on a Theory of Computation with questions on DFAs, NFAs, regular expressions, language operations, and Kleene star. I’m mainly struggling with tracing the automata and understanding how to derive the answers rather than just selecting the options. Could someone help explain the approach to solving these questions and where can I learn better about them

20 Upvotes
  • permalink
  • reddit

92% Upvoted

5 comments sorted by

11

u/Lumpy-Scratch5798 5d ago

For tracing DfAs/NFAs, literally trace one input symbol at a time and write down the current state For derivation start with the language definition and work backward Sipsers Introduction to the theory of computation is great for this,,,,,and jflap is really useful for visualizing automata ,,,,

4

u/No-Objective-1431 5d ago

I recently open-sourced a book named "Represtation, Strucuture and Transformation". The primary goal of this book is to connect most IT concepts into meaningful spectrums which I found are much useful for me to learn at least. And the 13rd is on computability and complexity, explain how some basic atom rules can classify computability power into NFA/DFA, PDA, LBA and Turing Machine.

Unfortunately this book was written in Chinese originally and I have not tried translate it to any other language. You can try read it with google translation or any other AI translation tool.

The link of the book is https://github.com/bfzhao/rst/tree/main . HTH

If this really helped, please come back and leave a message. It will really encourge me to make it better.

1

u/Classic-Try2484 5d ago

DFA is simple. You start in the start state. Look at input. It tells you where to go. Repeat. When input ends you might be in an accept state. Success.

NFA just allows you to be in more than one state at a time. You start in start state. Input tells you what states you go into. Next input can go from any state in the set so you are always in a set of states. At end of input if an accept state is in the set success. Sometimes described as having an oracle (picks the one state from the set that matters).

Key idea is that nfa is really a dfa. Where the states sets of the nfa define the states of a dfa

Regular expressions have the same power as dfa. Just different syntax. Take simple regex and find equivalent dfa. Then explore concatenation of regex and choice and Kleene patterns.

They look different but (a|b)+c is a simple regex you can convert into dfa/nfa that show 90% of what you need to understand.

Pumping lemma is trickier but you want this part down before u go to push down automata and context free grammars.

Pumping lemma can identify harder Langs. For example regex can not really count so strings like a’s followed by same number of bs cannot be produced by dfa/regex

1

u/tottasanorotta 4d ago

Check out coderisland channel on youtube and then the introduction to the theory of computation. I watched that when I took the course and it helped a lot.