Help me make a combined NFA for this languag

  • Thread starter Thread starter zeion
  • Start date Start date
AI Thread Summary
The discussion focuses on creating a non-deterministic finite automaton (NFA) and a regular expression (RE) for the language L1, which requires exactly one occurrence of the substring "dab" and prohibits the substring "bad." The user initially constructed two separate NFAs for each condition and is seeking guidance on how to combine them effectively. There is uncertainty regarding simplifying the combined NFA to derive a corresponding RE and how to implement a "trap" state due to varying paths to dead states. The user expresses frustration over the lack of responses regarding the creation of deterministic finite automata (DFAs). The thread highlights the complexities involved in automaton design for specific language constraints.
zeion
Messages
455
Reaction score
1

Homework Statement



Give an NFA and RE for each of the following languages.

L1 = {s \in {a, b, d}* : s contains exactly one occurrence of the substring "dab" and no occurrence of the substring "bad"}

Homework Equations


The Attempt at a Solution



I made two separate NFAs for each condition, then tried to combine them:Do they look right?
How can I simplify the combined one so that I can make a RE expression out of it?
I'm not sure how to make a "trap" state because the accepting states all have different paths to dead states?

Any help appreciated, thanks.
Thanks.
 

Attachments

  • e6-2aNFA_Bottom.jpg
    e6-2aNFA_Bottom.jpg
    5.7 KB · Views: 500
  • e6-2aNFA_Top.jpg
    e6-2aNFA_Top.jpg
    10.2 KB · Views: 474
  • e6-2aNFA.jpg
    e6-2aNFA.jpg
    5.8 KB · Views: 503
Last edited:
Physics news on Phys.org
No one knows how to make DFA's?
 

Similar threads

Comp Sci Regular expression to NFA -- confusing regular expressions-:
Replies
1
Views
2K
MHB Regular expression to NFA-confusing regular expressions-:
Replies
1
Views
1K
MHB Designing an NFA that accepts binary strings divisible by 5 or 6
Replies
6
Views
13K
How many words of length n are there in this regular language?
Replies
1
Views
2K
Program to display letter combinations on phone keypad
Replies
12
Views
3K
NP-Complete Problem: Determine if NFAs A and B Accept Same Language
Replies
1
Views
2K
Comp Sci C++ Array Help: Solve Troubleshooting Issues
Replies
1
Views
2K
Help me nail the final post to the fence of this algorithm
Replies
3
Views
1K
Engineering Solving an AC Circuit Problem with R, L, C Values
Replies
4
Views
1K
B How and why can multiplication combine physical quantities?
Replies
8
Views
2K

Hot Threads

Recent Insights

Back
Top