Help me make a combined NFA for this languag

  • Thread starter zeion
  • Start date
In summary, the conversation is about creating a NFA and RE for a certain language. The language is defined as containing exactly one occurrence of the substring "dab" and no occurrence of the substring "bad". The person making the attempt has created two separate NFAs for each condition and is trying to combine them, but is unsure about how to simplify the combined NFA and create a "trap" state. They are seeking help with this task.
  • #1
zeion
466
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: 450
  • e6-2aNFA_Top.jpg
    e6-2aNFA_Top.jpg
    10.2 KB · Views: 430
  • e6-2aNFA.jpg
    e6-2aNFA.jpg
    5.8 KB · Views: 456
Last edited:
Physics news on Phys.org
  • #2
No one knows how to make DFA's?
 

Related to Help me make a combined NFA for this languag

1. What is an NFA?

An NFA (Non-Deterministic Finite Automaton) is a mathematical model used to recognize patterns in strings of characters. It is commonly used in computer science and linguistics to represent and analyze complex languages.

2. What is a combined NFA?

A combined NFA is a single NFA that is created by combining two or more NFAs. This allows for the recognition of a larger language by combining the patterns recognized by the individual NFAs.

3. Why is it necessary to make a combined NFA?

Making a combined NFA allows for the recognition of a more complex language that cannot be recognized by a single NFA. It also simplifies the process of analyzing and manipulating the language by combining the patterns into one NFA.

4. How do you make a combined NFA?

To make a combined NFA, you first need to identify the individual NFAs that will be combined. Then, you need to determine how to connect the states and transitions of the individual NFAs to create a larger NFA that recognizes the combined language. This can be done through union, concatenation, or Kleene star operations.

5. What are the advantages of using a combined NFA?

Using a combined NFA allows for a more efficient and compact representation of the language, as multiple patterns can be recognized by a single NFA. It also simplifies the process of analyzing and manipulating the language, as there is only one NFA to work with. Additionally, combining NFAs can help to reduce the number of states and transitions, making it easier to understand and work with the language.

Similar threads

Comp Sci Regular expression to NFA -- confusing regular expressions-:
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
MHB Regular expression to NFA-confusing regular expressions-:
    • Programming and Computer Science
Replies
1
Views
711
HELP: Equivalence of NFA's with plugin DFA's
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
How to Construct an NFA for a Language Defined by Ternary Notation Conditions?
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
How many words of length n are there in this regular language?
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
[Pumping Lemma] About the cases for y in the xy^iz criterion
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
MHB Designing an NFA that accepts binary strings divisible by 5 or 6
    • Programming and Computer Science
Replies
6
Views
12K
Program to display letter combinations on phone keypad
    • Engineering and Comp Sci Homework Help
Replies
12
Views
2K
Computer Science theory doubts
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Help with DFA/NFA Homework | Solutions & Explanations
    • Engineering and Comp Sci Homework Help
Replies
3
Views
2K

Hot Threads

Recent Insights

Back
Top