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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [automata]

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

0
votes
1answer
22 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
21 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
28 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
17 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
47 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
0answers
23 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
0answers
21 views

why it said the “The left recursion has been removed at the cost of an extra non-terminal symbol(E1) and a little extra complexity”? [migrated]

When I read the book "A Practical approach to compiler construction" the chapter4 "approaches to syntax analysis" and the section 4.2.3.3 Left Recursion, it says: "The left recursion has been removed ...
0
votes
0answers
37 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
0answers
20 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$...
4
votes
0answers
138 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
35 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
45 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
14 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
28 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
20 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
44 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
10 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
37 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
42 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
26 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
20 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
29 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
48 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
64 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
19 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
95 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
21 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 ...
0
votes
1answer
24 views

Finding language accepted by a DFA

Our current DFA shown below, $M$, accepts binary strings with an even number of 0's and odd number of 1's. (since it only has accept state $q_1$). Suppose $q_1$ is no longer an accept state and $q_0$ ...
2
votes
0answers
20 views

Pumping lemma: Convert pumped, binary string $xy^iz$to integer

I am trying to use the pumping lemma to prove that the language consisting of the set of $0$'s and $1$'s, beginning with a $1$, such that when interpreted as an integer, that integer is prime, is not ...
2
votes
1answer
29 views

Does a finite state machine have to use all the input?

I'm trying to make a finite automata but am unsure about this detail. If the machine reaches the goal state before the input is finished, can the machine accept or does it have to continue going if ...
1
vote
1answer
21 views

How to compare indices of a string with a Pushdown automata?

I am attempting to construct a PDA of a language that looks like $\ {x\#y\#z}\ $ $x,y,z $ $\epsilon$ $\{ 0,1\}^{+}$ The PDA is nondeterministic, there are some other requirements, but primarily ...
0
votes
1answer
27 views

Context-Free Grammar / Automata

$$ L=\left \{ a^n b^m c^z : m \neq z, n \geq 1 \right \} $$ Can anyone have a look at my answer? Seems correct? $$ \\S\rightarrow TD|AR \\R\rightarrow bRc|Y \\X\rightarrow Xb|b \\Y\rightarrow Yc|c \\...
-2
votes
1answer
37 views

DFA with 2 Alphabets [closed]

I have got a problem working on a deterministic finite automaton. I have got 2 alphabets $\Sigma_a = \{a_1,a_2,a_3...,a_n\}$ and $\Sigma_b = \{b_1,b_2,b_3...,b_n\}$ the automaton should match a ...
1
vote
2answers
54 views

Write a minimal DFA for the language $L = \{(ab)^n \mid n \geq 0\}$

Write a minimal DFA for the language $L = \{(ab)^n \mid n \geq 0\}$ My attempt: I currently haven't completed the solution, but my main problem is to find a simpler solution for this as the ...
0
votes
0answers
54 views

Let G be the language of all string over {0,1} that do not contain a pair of 1s that are separated by a odd number of symbols.

This is a questions in book, Introduction-To-The-Theory-Of-Computation-Michael-Sipse, Third edition, P85. This is not hw problem(solution is given) So based on the given hit, we negate it first as F'=...
0
votes
0answers
39 views

How do I show that this DFA accepts this string?

We are given some DFA $M = (Q, \Sigma, \delta, s, F)$, with $l$ number of states in $Q$, where $M$ accepts a string $w \in \Sigma^*$ such that $|w| \geq l$. I want to show that if there are ...
-2
votes
1answer
29 views

Show that $L^D = \{ ww \mid w \in \{a, b\}^* \}$ may not be regular. [closed]

Suppose that $L$ is a regular language over the alphabet $\Sigma = \{a, b\}$. Show that $L^R = \{w^R \mid w \in L\}$ is regular ($R$ means reverse order). However, show that $L^D = \left\{ww \mid w ∈ \...
0
votes
1answer
85 views

Write a regular expressions for the set of strings over the alphabet Σ = {a, b} containing at least one a and at least one b.

Write a regular expressions for the set of strings over the alphabet Σ = {a, b} containing at least one a and at least one b. Would the correct answer be R= a* + b*
0
votes
1answer
26 views

Design a Deterministic Finite Automata (DFA) for 'abab'

Problem Design a deterministic finite automata (dfa) that satisfies the following: { w | w has 'abab' as a substring} Hence, ...
1
vote
1answer
21 views

Proof of regular expression

How can I prove that the following expression is regular $ab+(a^*+b)^*$ Is it enough to make NFA or DFA for this expression?
0
votes
0answers
27 views

i have to convert these of the following into regular expression… please guide me if its correct or not

 Language containing no words starting and ending on “a” RE= ba*b (none of the words generated from this expression with end or start with "a") L={bb,bab,baab,baaab,...}  Languages containing ...
2
votes
2answers
51 views

What is the Chomsky class of a language containing strings of a prime length?

I recently saw a Perl golf program that used a perl regex in a loop in order to test primality. Perl's regex's are strictly more powerful the regular expressions and applying them in a loop can be ...
0
votes
0answers
32 views

Converting NFA to DFA using TG and RE

how can I convert this NFA to DFA In school we are told that, to do this conversion first we have to convert this NFA to TG (transition graph) and then find the RE (regular expression) of TG and ...
2
votes
2answers
42 views

is a fractional i allowed in pumping lemma??

I checked the pumping lemma in many books(introduction to the theory of computation Michael Sipser) and website(wikipedia). they all give the same explanation:(definition from introduction to the ...
1
vote
2answers
88 views

Regular Expression VS Finite Automata

I am having a hard time to follow a concept from Introduction to the theory of computation (3rd ed.) by Michael Sipser. I got confused by the last sentence. Ok, we can convert regular express into ...
2
votes
1answer
57 views

Given regular language $L,$ prove $L'$ is regular

Given that $L$ is a regular language over some alphabet $\Sigma,$ prove that the language $L'=\{x_1x_2\cdots x_k\ |\ x_1,\dots ,x_k \in \Sigma\ \land \exists y_1,y_2,\dots y_{2k} \in \Sigma , \ ...