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".
 

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

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.

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.

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.

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.

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
Replies
1
Views
2K
Given specific v, dimension of subspace of L(V, W) where Tv=0?
Replies
15
Views
2K
Typical transistor design parameter [W/L]
Replies
1
Views
1K
Engineering Current density calculation in anisotropic ferromagnetic film
Replies
7
Views
2K
Help with DFA/NFA Homework | Solutions & Explanations
Replies
3
Views
2K
Are These Computer Science Languages Regular?
Replies
1
Views
2K
MHB Solve Sets of Form $v+X$ in $\mathbb{R}^2$
Replies
5
Views
1K
Is it ok to assume matrices A and B as identity matrix?
Replies
25
Views
1K
Two computational theory language questions - multi choice
Replies
5
Views
1K
What is v×w if v, a, and b have length 1 and w has length 2?
Replies
5
Views
2K

Hot Threads

Recent Insights

Back
Top