Designing a DFA for L={vwv : v,w elements of {a,b}* and |v| =2}

In summary, the language L={vwv : v,w elements of {a,b}* and |v| =2} requires a finite automaton that can remember the first two characters of the input and use that to match the last two characters. Starting with an automaton that accepts "vv" and modifying it may be helpful in constructing such an automaton.
  • #1
francisg3
32
0
L={vwv : v,w elements of {a,b}* and |v| =2}

I know that "v" can take either aa, ab, ba or bb as values. I also know that "w" can be any string containing "a" and "b". Overall, I know that the two first and two last characters must be identical. How would I show this in a DFA or even an NFA?


Thanks.
 
Physics news on Phys.org
  • #2
Think about which parts of the input the finite automaton must remember and how you can use that to keep a "running match" of the later part of the input. It may help to start with an automaton that accepts the language "vv" and see if you can modify that into one that accepts "vwv".
 

1. What is a deterministic finite automata (DFA)?

A deterministic finite automata (DFA) is a mathematical model used to recognize patterns in strings of characters. It consists of a finite set of states, a finite alphabet of input symbols, a transition function, a start state, and a set of accepting states. It can only be in one state at a time and the transition from one state to another is determined by the current state and the current input symbol.

2. What is the difference between a deterministic and non-deterministic finite automata?

The main difference between a deterministic and non-deterministic finite automata is in the transition function. In a deterministic finite automata, the transition from one state to another is uniquely determined by the current state and input symbol, while in a non-deterministic finite automata, there can be multiple possible transitions for a given state and input symbol.

3. What is the purpose of using deterministic finite automata?

The purpose of using deterministic finite automata is to recognize patterns in strings of characters. DFAs are commonly used in computer science and linguistics, where they are used to analyze and process regular languages, such as programming languages and natural languages.

4. What are the limitations of deterministic finite automata?

One of the main limitations of deterministic finite automata is that they can only recognize regular languages, which are a subset of all possible languages. They are also limited in their ability to handle non-deterministic or ambiguous patterns, as they can only have one possible transition for a given state and input symbol.

5. Can a deterministic finite automata be converted into a non-deterministic finite automata?

Yes, a deterministic finite automata can be converted into a non-deterministic finite automata, but the reverse is not always possible. This is because DFAs have a more restrictive transition function, so not all non-deterministic finite automata can be converted into DFAs without losing information.

Similar threads

Proof that its possible to generate NFA from DFA
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Given specific v, dimension of subspace of L(V, W) where Tv=0?
    • Calculus and Beyond Homework Help
Replies
14
Views
596
Engineering Current density calculation in anisotropic ferromagnetic film
    • Engineering and Comp Sci Homework Help
Replies
7
Views
730
Typical transistor design parameter [W/L]
    • Engineering and Comp Sci Homework Help
Replies
1
Views
937
Is it ok to assume matrices A and B as identity matrix?
    • Precalculus Mathematics Homework Help
Replies
25
Views
898
MHB Solve Sets of Form $v+X$ in $\mathbb{R}^2$
    • Linear and Abstract Algebra
Replies
5
Views
940
Alphabetic Design Elements - or: I've had too much coffee!
    • General Discussion
Replies
2
Views
447
Matrices: if AB=A and BA=B, then B^2 is equal to?
    • Precalculus Mathematics Homework Help
Replies
18
Views
2K
Computer Science theory doubts
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
What is v×w if v, a, and b have length 1 and w has length 2?
    • Calculus and Beyond Homework Help
Replies
5
Views
1K

Hot Threads

Recent Insights

Back
Top