Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [automata]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

0
votes
1answer
17 views

Find possible states in an automaton from a given input sequence

I have an automaton (specifically a nondeterministic finite automaton, NFA) and I am trying to determine the possible states that the automata could be in, given a specific sequence of input symbols (...
2
votes
1answer
43 views

What's wrong with this proof? (Regular languages)

We want to show that for any fixed $n$, $\bigcup_{i=1}^n L_i$ is regular when all $L_i$ are regular. I understand that this is only true for finite $n$. However, what's wrong with the following ...
-1
votes
0answers
62 views

Let $uv=vu$, Show $\exists w$ such that $u= w^{m}$ and $v = w^{n}$

I have to prove : Let $uv=vu$. Show that $\exists w$ such that $u= w^{m}$ and $v = w^{n}$. My progress: suppose $|v| \leq |u|$ then there will be some $b$ value such that $U = Vb = bV$. $$UV = VU....
1
vote
1answer
53 views

Proving $ww^Ru$ is not a regular language with Pumping Lemma

I'm trying to prove that $L=\{ww^Ru:w,u∈\{a,b\}^+\}$ ($w^R$ is the reverse of $w$) $w$ and $u$ cannot be empty strings. I want to prove this by using pumping lemma but I cannot find a good starting ...
-1
votes
1answer
30 views

Finite state automata

design DFAs for E={m,n}, that accepts the sets consisting of 1) All strings have at least one 'm' and followed by exactly two 'n'. 2) All strings have even no. of 'm' and odd no. of 'n'. where E ...
0
votes
1answer
26 views

Regular Language and Non-Regular Language

Regular Language as I know of, is something that can be defined by a FSM. Non-Regular Language is something that consists of repetition which cannot be stored by the FSM. I have found out that L( ...
3
votes
2answers
52 views

Does {a} \ {a} give an Ɛ in formal languages and automata?

I have a language L = {a}, alphabet Σ = {a} and I'm wondering, does the different of the same language give a language with an ...
1
vote
1answer
38 views

How to proof language which consists of concatenation of strings in palindrome is not a regular language?

How to proof $L = \{ x \in \Sigma^* | x=y_1\cdot y_2 \cdot \dots y_m, \exists m \ge 1 \,\land \forall y_i \in \text{Palindrome over } \Sigma^*\}$ is not a regular language? My attempted is $\text{Let ...
0
votes
1answer
37 views

If $A$ is not a regular language and $B$ is a regular language and $B \neq \varnothing$, does $AB$ is not regular language?

I am trying to proof that $L = \{ 0^11^2...0^{n-1}1^n0^{n-1}...1^20^1\}$ where $n >= 0$ is not a regular language. So my method is to put $S = 0^11^2...0^{n-1}$ $W = S1^nS^R$ And then proof $S^...
1
vote
2answers
24 views

Showing that a Language is regular using a state machine diagram

I'm in my first few weeks of taking a theoretical course at my school and was wondering what is wrong with my answer to this question. I've been told to show that the language: L = {x | x has even ...
1
vote
0answers
34 views

Converting NFA to DFA. Loops and exits.

Task Convert the following NFA to a DFA. My process Our goal is to achieve the following L(M'') = L(M') = L(M) where M is our NFA and L(M) is the set of all strings that M accepts. Make sure that I ...
1
vote
1answer
41 views

String powers. Lemma 1.3.5 in word processing in groups. Epstein.

I can't understand this demonstration. Why if ${w'}_1$ is different from ´${w'}_2$ then we have that $f(u)$ and $v'$ are powers of some string $z$?
0
votes
1answer
95 views

Simply starred language. $\left\{(ab)^n:n\in\mathbb{N}\right\}$ it is regular?

I have many doubts with this. First: In the definition, let $A=\left\{x\right\}$ one-letter alphabet. Then $A^{\ast}$ is simply starred? Second: In the definition, I know that $\left\{a^nb^n: n \in \...
1
vote
0answers
18 views

Decidability context-sensitiv and context-free grammars

Show that it is unsolvable whether a given context-sensitive language is context fre. And, show that the emptiness problem is solvable for one-way nondeterministic stack automata. I don't know how ...
1
vote
0answers
31 views

Equivalent grammar

Consider the grammar $G=(\{S,A,B\},\{0,1\},P,S)$, where $P$ consists: $S\to AB$ $A\to BSB$ $A\to BB$ $B\to 0A1$ $B\to 0$ $A\to 1$ $B\to e$ Find equivalent grammar for which S does not appear ...
1
vote
1answer
51 views

Conversion of Epsilon NFA to DFA

on the following problem: Convert the following ε-NFA to DFA and prove if it is equivalent or not with the A2 in the picture enter image description here i think that the epsilon closure of the {3,8} ...
2
votes
1answer
27 views

Is it ALWAYS true that if L= {w|odd(w) is regular} then L is regular.

I have been stuck on this problem for a couple of hours and can't seem to figure it out.A bit of a hand would be nice.So we have that odd(w) is the letters from the string w that are in odd positions ...
0
votes
1answer
35 views

Finite automata where the difference in the number of a's and b's is less than three

Given the following problem: Design a finite automata that only recognizes the strings of the language $L$ of the alphabet $\sum = \{ a, b \}$ such that each string does not contain any prefixes ...
2
votes
1answer
30 views

Given a finite automaton determine if it is deterministic and indicate regular expression

Given the finite automaton: Make the transition table and indicate if it is deterministic or not. Indicate which of the following regular expressions corresponds to the language recognized by the ...
1
vote
0answers
20 views

Define a grammar from the alphabet $\{ a, b \}$ which accepts the string $w$ where $\#_{w(b)} \leq \#_{w(a)} \leq 2 \#_{w(b)}$

Given the following problem: Define a grammar that only generates all the strings from the language of the alphabet $\sum = \{ a, b \}$ such that the number of letters a is more than or equal to ...
0
votes
1answer
38 views

Convert Context-Free Grammar to Automata

I am trying to convert the following grammar to an automata: Let $S$ be the start symbol. $S \to aQc$ $Q \to aQc$ $Q \to aaRbb$ $R \to aaRbb$ $R \to \epsilon$. But I don't fully understand how to ...
1
vote
1answer
22 views

Is a minimal image of an automaton a F-clique?

Let $A = (Q,\Sigma, \delta)$ a finite complete deterministic automaton. Let's call $image$ the set $Qs$ for some word $ s \in \Sigma $ . I'm wondering if the following definitions are equivalent: ...
2
votes
1answer
32 views

Construct a grammar that generates the language $L = \{ a^x b^{x-y} c^y \mid x > y > 0 \text{ and } (x + y) \text{ is even }\}$

I have the following problem: Construct a grammar that only generates the strings that belong to the language $L$ where: $$ L = \{ a^x b^{x-y} c^y \mid x > y > 0 \text{ and }(x + y) \text{ ...
1
vote
1answer
19 views

equivalence of finite state and regular expression

Consider the following theorem: Theorem: If L=L(A) for some DFA A, then there is a regular expression R such that L=L(R) Proof: Let A's states be: {1,2,3,....n} for some integer n. Let $ R^k_{ij}$...
1
vote
1answer
61 views

DFA accepts only one state

Consider the NFA that accepts the language L such that: L={w| second last symbol in w is one} Now, the NFA diagram for this is: Now the corresponding DFA diagram for this would be: Now, lets ...
0
votes
1answer
36 views

Deterministic finite automaton (DFA) for regular expression $(a|(bc)^n)^m$

I constructed a machine for the regular expression $(a|(bc)^n)^m$ where $n,m > 0$. I would be very interested in a correction of the machine, or is the machine in its form correct? My DFA: Thanks ...
0
votes
1answer
70 views

Prove that $L= \{w|$ $w $ ends with a palindrome of length greater than or equal to $4\}$ is nonregular using the pumping lemma.

The alphabet is $\{a, b\}$ Hi, I tried this: Assume to the contrary that $L$ is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s$ be the string $a^{p}ba^{p}$. Because $s$ is ...
0
votes
1answer
32 views

Regular expression: Difference between $\emptyset$-concate and $\lambda$-concate?

Given the definition below, is that the concatenation $\emptyset A$ the same as $\lambda A,$ given $A$ a regular expression? If not, what's the difference? My guess is that if I take concatenation $AB$...
5
votes
0answers
149 views

Can we decide if a dragon comes home?

First, a quick definition: A (deterministic) Lindenmayer system (L-system) over an alphabet $\mathcal{A}$ is essentially specified by a function $f:\mathcal{A}\mapsto\mathcal{A}^*$ (where $\mathcal{A}^...
0
votes
0answers
35 views

Equicontinuity or mean equicontinuity?

Can someone provide some examples to illustrate the difference between equicontinuity and mean equicontinuity? Can someone provide a concrete example that is mean equicontinuous but not ...
0
votes
2answers
37 views

What is regular expression and its NFA of a word that accept any number that is divisible by 5?

I was given a task to find RE and NFA for a word that is divisible by 5. ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} String passed to RE could be of any length You may ...
0
votes
1answer
48 views

Prove $L$ is context free if $L_1$, $L_2$, $L_3$ are regular by building a suitable grammar

Given $L_1$, $L_2$, $L_3$ are regular, prove that: $$L=\{w_1w_2w_3\space|\space w_i\in L_i\space \land\space|w_1|+|w_2|=|w_3| \}$$ is context free by building a suitable context free grammar. I know ...
1
vote
1answer
22 views

Subset of Context Free Language with Strings Starting and Ending in Same Symbol is Context Free

This was a question asked in a previous exam that I'm studying. Assume $L$ is a context free language (CFL). Let $L_{a..a}$ be a subset of $L$ s.t. all strings in $L_{a..a}$ start and end with the ...
0
votes
0answers
37 views

Proving that a language is recurive

I was given the next language: $L$= {$<M2>$ | $M2$ is a turing machine , $L(M1)$=$L(M2)$ and |$<M2>$| = |$<M1>$| } I was asked to prove that $L$ is recursive, but how do I do it ...
1
vote
1answer
32 views

Is $\{a^n b^n c^{2n} \mid n \geqslant 0\}$ a context-free language?

I tried to solve this excersize but get two different answers I know that we can do homomorphism $$ h(0)→a,h(1)→b,h(2)→cc $$ and $h^{-1}(L)$ = {$0^n 1^n 2^n | n \geqslant 0$ } that is not CFL ...
0
votes
1answer
28 views

Context-Free Grammar to Pushdown (Stack) Automata

Given the following problem: Convert the following Context-Free Grammar specification to it's corresponding Pushdown (Stack) Automata. $$ G = (N, \sum , P, S) \\ N = \{ S, A \} \\ \sum = \{ 0, 1 \}...
1
vote
1answer
22 views

How to prove that a language which clones is regular?

I am trying to prove that the following language is regular: $L'$ is a clone of $L$ where $L$ is a regular language over $\{0,1\}^*$. For example, if $L=001$, then $L'=000011$. If $L=010$, $L'=001100$...
0
votes
2answers
45 views

a hard mapping reduction problem

let L={(M1),(M2)|M1,M2 are TM's and L(M1)={(M)| M is a TM and M2 accepts (M)}} so my guess is L is not in RE but im having a hard time finding the right mapping reduction....any ideas ?
0
votes
0answers
11 views

Encyclopedia of Automata Types

Wondering if there exists a comprehensive list of automata types (finite automata, tree automata, register automata, etc.). Something along the lines of Encyclopedia of Proof Systems. Or just ...
0
votes
0answers
43 views

Context Free Grammar - Middle of an Even Binary String

I am new and practicing automata and language theory. I found this problem where I have to construct a grammar that consist of all strings under the binary values in which the middle symbol is $1$. e....
0
votes
0answers
45 views

What is the difference between $\{0,1\}$ and $\{0,1\}^*$?

I am trying to understand the difference between the alphabet $\Sigma = \{0,1\}$ and $\Sigma = \{0,1\}^*$ For $\Sigma = \{0,1\}$. I searched online and found that it can be {$\epsilon$, 0,1,00,01,10,...
0
votes
1answer
27 views

Help me check my Automata from given Grammar

My update : Find Automata for $G = (V, T, S, P)$, where $V = [0, 1, S, A, B]$ and $T = [0,1]$ and $P = \{ S -> 1B, S->0, A->1A, A->0B, A->1, A->0, B->1\}$ Please look at ...
0
votes
0answers
21 views

How can you construct an NFA with k+2 states, where k is an arbitrary natural?

I was asked this question and couldn't come up with an answer? If I had a language $X = \sum^{*} a \sum^{k}$ where $k$ is an arbitrary natural number (the language where the $k+1$'st to last letter ...
1
vote
0answers
33 views

Finite State Machine with outputs(Mealy or Moore Machine) [closed]

Construct a finite-state machine for entering a security code into an automatic teller machine (ATM) that implements these rules: A user enters a string of four digits, one digit at a time. If the ...
3
votes
3answers
49 views

Verify language that i found of this automata

Sorry for my bad english. Automata: My answer: $$L = \{0^n, 0^n1X \mid n = 1,2,3\dots\}$$ X is any strings that is not empty.
1
vote
2answers
70 views

What is wrong with my application of the Myhill-Nerode theorem on this language?

Let $L=\left\{ w\in\Sigma^{*}\mid w\text{ has an equal number of 01 and 10}\right\}$ (e.g. $010\in L$) over $\Sigma=\left\{ 0,1\right\} $ I initially tried to prove that $L$ is not regular Proof:...
1
vote
1answer
24 views

Design DFA for $ (a + b(ba)^*)^*b$

I'm having some trouble to design a DFA that accepts the language defined by this regular expression $(a + b(ba)^*)^*b$ Can I say that $(a + b(ba)^*)^*$ is the same as $(a + b)^*$ ? Given this ...
1
vote
2answers
140 views

Creating a deterministic Finite state machine that accepts even 1s parity

Ive been working on this project for over a week now and its coming due soon, and im in no way going to finish it soon. the project is essentially where we have been assigned 3 "Codes" which form a ...
1
vote
1answer
37 views

Regular properties of a graph

Could anyone provide me with a list of graph properties that are regular? I do not mean the definition of a regular graph, I mean graph PROPERTIES. Why am I asking this? Well, while revisiting the ...
1
vote
1answer
22 views

Generalizing Regular Expression from FAs

if we want to generate a regular language for this FA, it would be (1 ∪ 0(00 ∪ 11)* (01 ∪ 10)) ◦ ((00 ∪ 11) ∪ (01 ∪ 10)(00 ∪ 11)* (01 ∪ 10))* Let's challenge ...