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.

Filter by
Sorted by
Tagged with
0
votes
0answers
21 views

PDA Explanation

{a^2i.b^3i | i ≥ 0 } How would I draw this? I just started learning about pda's and I'm not sure where to start. I've looked at youtube videos explaining pda's but I'm still not understanding how to ...
0
votes
1answer
36 views

Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$

This problem is from an exercise sheet so it would be nice if you could guide me to the solution. The problem: For $ k \in \mathbb{N}\setminus\{0\}$ let $$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}...
0
votes
1answer
33 views

Cannot determine if this language is context-free or not

L2={w e {0,1,2}* : w has the same number of 1's and 2's} I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 is pushed onto the stack,...
0
votes
0answers
14 views

Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1| A -> 0A|1A|𝜖 How can i interpret the odd number of 1's also?
1
vote
1answer
42 views

Turing machine state transition diagram vs finite state machine state transition diagram

If you were given a state transition diagram could you tell, just by looking at the diagram, if the diagram represented a DTM or a DFA (especially if it was unlabeled, just a directed graph)? Would ...
0
votes
1answer
24 views

Create an Finite Deterministic Automata for a regular expression

I want to create a finite state machine that accepts the following language: $$ L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\} $$ So I began by writing a regular expression ...
0
votes
1answer
24 views

How do i prove this language is regular? [duplicate]

I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?
1
vote
1answer
536 views

What does it mean for a grammar to be LR(0)?

I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0). For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
0
votes
1answer
39 views

Converting Moore to Mealy When first Node has Output

This is a homework question, which I am able to do, except my teacher failed to mention what to do when the very first node has a 1 output. I've looked through online examples, and I'm sure this has a ...
1
vote
1answer
37 views

How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
1
vote
1answer
17 views

Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?

I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG). I suspect that languages like $\text{L} = \{...
0
votes
1answer
44 views

Convert finite automata to regular expression

I am trying find the regular expression that describes the finite automata in the image below. Given the following finite automata which of the following regular expressions describes the same ...
1
vote
2answers
31 views

Regular language is closed given transposition of rightmost character to leftmost

It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I'...
0
votes
0answers
10 views

I'm having some trouble converting a FA to a RegEx [duplicate]

I was reviewing some of the material that I found about FA to RegEx and while I was practicing with one or another conversion, I came across this FA that I could not pass to RegEx. Would someone be so ...
1
vote
2answers
39 views

DFA to accept a String containing even number of both A and B, but rejects empty String

I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(ε) I have already drawn the DFA which accepts the above language, without rejecting the ...
1
vote
1answer
32 views

DFA and equivalence relation

I was studying Theory of Computation and I'm kind of lost in solving this problem. Let $R$ be a relation defined on the set of states $Q$ of a DFA as $q_1Rq_2$ if $\delta(q_1,a)=\delta(q_2,a)$ for ...
1
vote
0answers
21 views

Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?

Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular. If we assume on the contrary, then there ...
1
vote
2answers
24 views

Operations without common elements can not be generated using a finite state automata

I heard that some operations involving regexes that do not have common elements can NOT be generated using a finite automata. I do not remember what it was, where it was from, can anyone tell me what ...
0
votes
0answers
14 views

Is that a regular express? Proof using closure properties or pumping theorem [duplicate]

I am studying regular express. I understand how to proof a xa ya. However, I don't know how to proof the below problem. Please help me. L = { xa yb | a ≠ b }
0
votes
1answer
25 views

Is (a+b)* and (ab)* same in finite automata?

Regular language of (a+b)* and (ab)* are: (a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...} (ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... } I am new to Finite automata and this simple notion is ...
0
votes
2answers
31 views

What does this language notation specify?

I am given this exercise: Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ∈ L1L2. w1=ε w2=aabbcc w3=abbccw w4=aabbcccc w5=...
1
vote
2answers
33 views

Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma

I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma. My idea here was to use the string $ s = (...
1
vote
1answer
31 views

Applying the Pumping Lemma to aspecific string

Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$...
0
votes
0answers
40 views

NFA recognizing strings in $\{0,1\}^*$ that have two zeros separated $4i$ characters, for some $i\geq1$

I am trying to design a nondeterministic finite automaton that recognizes the language of strings in $ \{0,1\}^{\ast}$ that have two zeros separated by a string of length 4i, for some $i \geq 1$. Let $...
0
votes
2answers
22 views

string concatenation vs language concatenation

What exactly is the difference between $$ C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\} $$ and $$ D = \{a^nba^nba^nb | n \geq 0 \} $$ It is known that D is non-regular and C is regular, but I am not sure ...
2
votes
2answers
37 views

How to we prove if a right linear language is ambiguous?

Considering the following language as an example: $$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \\ D ...
0
votes
1answer
33 views

Read regular Expression from NFA

Good evening everyone! Can someone help me with the following task? So we have this NFA: I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
0
votes
1answer
108 views

What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)

I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as $(0+0001)((1111)^*+(00)^*)$ What is the length of the longest string ...
2
votes
3answers
42 views

How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?

I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA. I'm thinking to have n+1 states in a NFA, with the start state as the ...
0
votes
1answer
24 views

minimum number of states in cross product of two minimum DFAs

If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
1
vote
2answers
55 views

How to prove that concatenating a language A and A* is commutative?

Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far. If $A$ is ...
0
votes
0answers
86 views

Generalization of automaton - Sipser example 1.33

I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure that my transition function is wrong. I'd like ...
0
votes
0answers
29 views

Building an NFA where where proceeding part of string has same or more 1's

Having trouble figuring out a NFA for the following language, the objective is to use only 3 states: $L = {\{1^ky : y \in \{0,1\}^* }\text{ and y contains atleast k 1's, for k} \ge 1 \}$ I have got to ...
1
vote
1answer
73 views

Expert explanation of state elimination methods [duplicate]

I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method". In other words, what is the general idea, and what is the ...
1
vote
2answers
37 views

How are useless states created NFA to DFA

So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA ...
0
votes
1answer
78 views

Understand the DFA: accepting or not accepting “aa” or “bb”

I want to discuss the strings accepted by couple of DFAs: DFA in Figure 1 has 3 final states. It looks like that it accepts both the substrings "aa" (q0q3q0q1) or "bb". So this is ...
2
votes
1answer
12 views

Sufficient condition for $xy^*z \subseteq L$ for a DFA with $n$ states

In chapter 2 of the New Turing Omnibus, the author considers an unknown finite automata with 6 states. Through trial and error, it is deduced that the words 0101, 0100101, 0100100101 are accepted. It ...
1
vote
2answers
14 views

PDA for a language where the second part is not the reverse of the first part

I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where $L \subseteq ({a,b,c})^*$ So $n$ and $m$ are both a ...
1
vote
1answer
19 views

A regular language derived from another

This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular: $$ \{x|\exists y \; |y| = 2^{|x|} ...
0
votes
1answer
35 views

Can this language be called regular?

Recently, I was facing some problems in effectively proving the following : Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
2answers
67 views

How can I efficiently construct a CFG from a language

I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}. So m can be infinitely bigger than n but n can ...
1
vote
1answer
31 views

Regularity of a language constructed from a know regular language

I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language: $$ \{x|\...
1
vote
1answer
28 views

Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states

Let $L$ be a language, and consider the following relation $\equiv_L$ on strings: $s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$. This is ...
1
vote
1answer
68 views

Clarification on an Hopcroft book DFA minimization example

At page 156 there is an example on how to find the distinguishable states for the following automaton: The following table shows the distinguishable states: By applying the given definition for ...
1
vote
1answer
114 views

Check if a NFA accepts a string of non-prime length

Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number. My ...
0
votes
1answer
52 views

What language does this deterministic finite automaton accept?

Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If ...
2
votes
1answer
61 views

Extracting regex submatch boundaries without backtracking

I'm attempting to develop from scratch a simple regex engine. I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index and ...
4
votes
1answer
161 views

Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular

I try to show that this language is regular: $L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ If I build a NFA and run on it every substring of w (skip other letters ...
3
votes
2answers
111 views

Is it possible to construct a finite state automata for a decimal adder?

Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $\Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is ...
-2
votes
1answer
46 views

running RAM on a given input

I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance, there's a Random Access Machine which has an input {0,1}*. The ...

1
2 3 4 5
28