Help me make a combined NFA for this languag

  • Thread starter Thread starter zeion
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on constructing a combined Non-deterministic Finite Automaton (NFA) for the language L1 = {s ∈ {a, b, d}* : s contains exactly one occurrence of the substring "dab" and no occurrence of the substring "bad"}. The user initially created two separate NFAs to address each condition but seeks guidance on simplifying the combined NFA and deriving a regular expression (RE) from it. Key challenges include the creation of a "trap" state due to differing paths to dead states among the accepting states.

PREREQUISITES
  • Understanding of Non-deterministic Finite Automata (NFA)
  • Knowledge of regular expressions (RE)
  • Familiarity with state machine concepts
  • Experience with automata theory
NEXT STEPS
  • Research methods for combining NFAs, specifically using the subset construction technique
  • Learn about creating trap states in finite automata
  • Study the process of converting NFAs to regular expressions
  • Explore examples of NFAs that enforce specific substring conditions
USEFUL FOR

Students of automata theory, computer science enthusiasts, and anyone involved in formal language processing or compiler design.

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