Questions tagged [finite-automata]
Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.
1,753
questions
3
votes
2
answers
127
views
in NFA is every state itself contained in set generated by transition function when considering epsilon transition from that state?
in $\epsilon$-NFA (NFAs involving $\epsilon$ transitions) when we have $\epsilon$ transitions, I understand it as where can we go if we don't read any symbol from the input tape, then I think every ...
0
votes
1
answer
18
views
What is the set FirstHalves B? You can simply write out the set explicitly, enumerating the first four values
For any set of strings A, define the set FirstHalves A = {x∣∃y such that len(y) = len(x) and xy in A }. For example, FirstHalves {01, 111, 1010, 001101, 1011} = {0, 10, 001}, ie the first halves of ...
1
vote
0
answers
38
views
A proof that $a^n b^m $ for $n\neq m$ is not regular by using the pumping lemma
I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular.
This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems.
...
1
vote
3
answers
73
views
Subset Relations Between CFGs and Their Languages
Is it possible for there to exist two context-free grammars where the set of rules of the first is a proper subset of the set of rules of the second, yet the language generated by the second grammar ...
1
vote
1
answer
51
views
Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}
So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of 10
I created a DFA that could satisfy this requirement,...
-1
votes
1
answer
30
views
What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?
I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where:
two versions: one that starts and ends with 0, the other that starts and ends with 1
connected by plus, which does not mean union of both ...
-3
votes
2
answers
44
views
A more concise Finite Automata for 10 substring?
I am learning about finite automata and trying to create a machine that matches
{w ∈ Σ∗| w does not contain the substring 10}
I created a DFA where it either starts ...
1
vote
2
answers
54
views
Shortest regular expression possible
The question asks to write the shortest regular expression possible to the following automaton:
I see only one way to tackle the problem:
Use one of the methods mentioned here How to convert finite ...
-3
votes
1
answer
31
views
How to convert the following from NFA with ε-moves to DFA?
Can you provide the transition table along with the solution for better understanding?
-1
votes
1
answer
34
views
Construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa"
I want to construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa". I tried to follow the same procedure as in all the words ...
0
votes
2
answers
78
views
regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$
The question asks to write down a regular expression $r$ indicating the language of all the words above $\Sigma = \{a, b\}$ , in which the number of $a$ is even and there is no sub-word $aab$ in them.
...
1
vote
2
answers
76
views
Resources on Moore and Mealy Machines
I was studying about Moore and Mealy machines but having hard time connecting with them because 1) they are different from typical normal machines.what is the need of "output" and 2) My text ...
0
votes
1
answer
59
views
DFA that accepts strings ending with an even number of 1 in the last three characters ("000","110","101","011")
I need to design a binary DFA to accept strings where the last three characters read are either "000", "110", "101" or "011". My brutal solution is:
I need ...
-3
votes
0
answers
62
views
Find a regular grammar that generates words with even number of a's and find a regular grammar that generates words with odd number of a's
I have a question about solution of these two exercises: Find a regular grammar that generates words with even number of a's and find a regular grammar that generates words with odd number of a's. ...
2
votes
1
answer
40
views
Create NFA where |w|_a is divisible by 2 or |w|_b is divisible by 3
I have to create an NFA $\mathcal{A}$ that accepts the language $L = \{w \in \Sigma^* \ | \ |w|_a \ \text{is divisible by 2 or} \ |w|_b \ \text{is divisible by 3} \}$
So the NFA only accepts words ...
1
vote
1
answer
62
views
How to show L is non-regular without pumping lemma?
$L=\{(ab)^n : n\text{ is a natural number apart from }6\}$, I want to show L is non-regular by finding an infinite set of L-distinguishable words. Could you help me?
0
votes
1
answer
16
views
Hardwiring input in DFAs and PDAs
A Turing Machine can be converted into a Turing Machine that has a specific input coded into it's description. This Turing Machine can then be run on empty input. Can we do the same for PDAs or DFAs?
...
4
votes
0
answers
118
views
Constructing worst case for L* by D.Angluin
I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
3
votes
1
answer
165
views
Difference between product automaton vs. NFA with epsilon transitions
Let $L_1, L_2$ be regular languages.
You can proof with a product automaton that $L_1\cup L_2$ is also regular.
But you can also construct a NFA. Since $L_1, L_2$ are regular, they also have an NFA ...
2
votes
1
answer
265
views
Pumping Lemma Applied to 3 Variables
Prove That the Language
$L_1 = \{0^i1^j0^k | i < j\ or\ i > k\}$
is not regular using the pumping lemma.
I am not sure how to begin with this I ended up using the string:
$0^p1^{p+1}0^{p+1}$
S = ...
1
vote
1
answer
55
views
Provide a 2-state DFA for L={a}∗{b}∗ , the set of words of the form aa⋯abb⋯b
I'm kinda confused on how to construct this DFA. I'm trying but keep running into the problem of reading an a after the b's or what to do if starting with a 'b'.
0
votes
1
answer
34
views
Trouble proving this is regular
I'm taking an automata class and one of the examples is showing this is regular. My initial thought was to make a DFA to show it is but i'm a bit confused on what a DFA with a standard 5 tuple would ...
1
vote
1
answer
61
views
Why can't we prove closure under concatenation using DFA?
I can't understand why do we have to use NFA to prove that concatenation operation is closed. According to sisper's book it says that we can't determine where to split the string, i.e. where to ...
2
votes
2
answers
1k
views
Converting Regex to DFA
People I know said that converting a Regex to DFA is just a "matter of judgement" (I do not believe them, there has to be a more systematic approach).
Is there a simple/intuitive, yet ...
2
votes
1
answer
38
views
What does the language of DFA of LR itemsets represent?
As we know, if we want to make a $LR(0)$ (say) parsing table for a context free grammar (CFG), we prepare the $LR(0)$ itemsets with $.$ (dot) in RHS of the CFG production.
With this $.$ we keep track ...
0
votes
1
answer
97
views
NFA for the language that accepts binary strings ending with 00
This is the question:
1.7. Give state diagrams of NFAs with the specified number of states recognizing each
of the following languages. In all parts, the alphabet is {0,1}.
a. The language {w| w ...
0
votes
0
answers
60
views
How to work thompson's construction algorithm?
Could someone explain to me, through an example, how the McNaughton–Yamada–Thompson algorithm works in a way that I can understand?
Thank you in advance for your helpful response!
-1
votes
1
answer
41
views
Is this correct Context free grammar(CFG) for these two languages?
Question 1: L = { 0^n 1^n | n > 0 }
My answer = S -> 0 S 1 | 10
Question 2: L = { 101^n0^2n | n > 0 }
My answer = S -> 101 S 00 | 100
Can anyone correct this if there is any issue with ...
1
vote
0
answers
28
views
In regular language inference, how is the observation table kept consistent?
I am trying to understand the background literature on regular language inference in the TTT paper ("The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning" by Isberner, ...
1
vote
1
answer
111
views
How to construct complement of NFA universality?
Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal?
I tried to use the fact that NFA-universality is PSPACE-...
2
votes
1
answer
100
views
Applications of ω-automaton in engineering
Finite automaton is a well-known topic which finds applications in software engineering (e.g. pattern matching or regular expressions in general).
ω-automaton are another kind of automaton, defined ...
0
votes
1
answer
51
views
Determining the language of a DFA
I've tried quite a large amount of examples, starting from 1 bit all the way up to 5 bits yet I couldn't put my finger on any recurring pattern of words that are accepted.
the DFA is as such:
The ...
1
vote
1
answer
250
views
How to build a deterministic or non deterministic finite automat for a language
$L_1$ and $L_2$ are two languages that have a finite deterministic automaton. $Σ = \{0,1\}$ for the two languages.
Let $L=\{x∈L_1\mid \text{there exists } y∈L_2,\text{such that } \#_0(x)=\#_0(y)\}$, ...
0
votes
1
answer
62
views
Proving that the intersection of two languages is regular or not?
Let $B$ and $C$ be two languages on $A = \{a,b\}$:
$B = \{ w \mid w \text{ has the same number of }a\text{ and }b\text{ symbols}\}$
$C = \{ a^n b^m \mid n,m \ge 0\}$
Describe $B \cap C$ and determine ...
0
votes
1
answer
57
views
Intersection of a regular and a non-regular language can give a non-regular language?
Determine two languages L and L1 on the alphabet {a,b} with regular L, L∩L1 is non-regular and L1 does not contain L.
I came up with this solution:
L = { w | w ends with the string aba}
L1 = {w | w = ...
0
votes
2
answers
65
views
Can the intersection of 2 non-regular languages be a regular and infinite language?
The outline of the exercise is this:
Describe two non-regular L1 and L2 languages on A = {a,b} such that L1∩L2 is infinite and regular.
The proposed solution to this exercise is:
L1 = {a^n b^n | n >...
0
votes
1
answer
40
views
Proving a language is not regular using Pumping Lemma
So I am given the language qr where q is any combination of a's and b's. r is then the reverse of whatever q is. For example, abba is in the language because we can make a q = ab and r = ba
I have to ...
1
vote
0
answers
12
views
Is there a symbol in FA/FSM for everything else
I remember in a Computability Theory class building a state machine for an assignment that required many 'go-back' transitions on $\Sigma - symbols$ for all symbols not already handled. This was very ...
0
votes
0
answers
38
views
Can someone explain the following NFA?
I'm learning NFA and the following question is confusing me.
Can Someone explain the answer. I have a feeling that it might be wrong.
Thank you!
-1
votes
2
answers
305
views
Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}
I am attempting to draw the DFA of this problem but I'm kind of stuck. In another post I saw that the DFA should have 10 states. I'm finding it hard to even understand the question, is the input to ...
0
votes
0
answers
51
views
1 way 2 stack and 2 way 2 stack Pushdown Accepters that accepts $L=\{a^{(n^2)} \mid n \geq 1\}$
Using a 1 way 2 stack, and a 2 way 2 stack PDA, I want to check if the length of an input string is strictly a perfect square number. How can I do this in both approaches?
0
votes
2
answers
67
views
Why does lexer has O(n) time complexity?
According to my CS knowledge so far, a lexer uses DFA(which takes linear time) for 'each' token type to find the next token, so in the worst case, it should try 'all possible' token types of a ...
0
votes
2
answers
113
views
How to find prefixes and suffixes for infinite languages? (Automata)
L= {abc}
prefix = {epsilon,a,ab,abc}
suffix = {epsilon,c,bc,abc}
It's easy to find suffixes and prefixes for finite Regular languages. But what will be the ...
0
votes
0
answers
145
views
Turing machine for a^n b^m c^n d^m
The state diagram for the initial part of this turing machine given as:
Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
0
votes
0
answers
33
views
What is the minimum length word accepted by the product of these simple loop automata?
Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^* $ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ ...
2
votes
1
answer
99
views
What is the Minimum length of a string that is accepted by a DFA that shows that the language accepted by that DFA is infinite?
What is the minimum length of a string that is accepted by a DFA, shows that the language accepted by that DFA is infinite?
I checked this post How to determine if an automata (DFA) accepts an ...
0
votes
1
answer
117
views
Construct a regular grammar that produces all possible strings of $\Sigma = \{a,b\}$ that do not contain substring 'abba'
I'm really stuck here and do not know what to do. So far, I've constructed a DFA and a regular expression that produces the aforementioned set of strings. Namely, the DFA looks like:
After a lot of ...
1
vote
1
answer
70
views
DFA for even concatenation of strings from a language
If I have a deterministic finite automaton (DFA) with a language $W$, and I need to create another DFA that returns all the strings that are a concatenation of an even number of strings in $W$, how ...
0
votes
0
answers
52
views
After converting a CFG to a PDA, what is an example input string to the PDA?
For example, the following CFG:
S$\rightarrow$aSb|$\epsilon$
A valid string within the language described by the CFG would be, e.g., "aabb".
The converted PDA has the following form:
The ...
0
votes
0
answers
44
views
Binary combinatorics with rank
I am looking at finding acceptable binary values with maximum 2 consecutive 1s and 0s, from a range of maximum 6 bits (2^6 values).
Also, I want to rank and unrank these subset of values (in ...