Skip to main content

Questions tagged [automata]

Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.

Filter by
Sorted by
Tagged with
-1 votes
1 answer
41 views

Regular languages: words from A that do not contain any word from B as a substring

How to prove, by construction and/or regular closures, that if $A$, $B$ are regular then the language $L$ defined by $$L=\{w\mid w\in A,\ \not\exists y\in B\ :\ w=xyz\text{ for some }x,z∈Σ^∗\}$$ is ...
user169627's user avatar
0 votes
1 answer
47 views

NFA for $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$

The question asks to write a NFA for the following language $L$ above $\Sigma = \left \{0,1 \right \}$. $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \...
Daniel's user avatar
  • 47
0 votes
1 answer
54 views

Regex for $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = 4 \text{ contains the character } 0 \}$

The question asks to write a regex to the following language $L$ above $\Sigma = \left \{0,1 \right \}$. $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = ...
Daniel's user avatar
  • 47
0 votes
1 answer
25 views

NFA for a regular expression without $\epsilon$-transitions

I think I know how to convert a regular expression to NFA without requiring epsilon transitions, but I'm not sure if I'm right (I'm just using common sense to be honest, no particular algorithm in my ...
Acad's user avatar
  • 101
0 votes
1 answer
46 views

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Consider the language $L$ over the alphabet (,[,),] such that any word $w \in L$ if formed as a shuffle of two (possible empty) well-formed sequence of parenthesis: one over (,) and another over [,]. ...
kerzol's user avatar
  • 103
-2 votes
0 answers
18 views

What is the grammer of L = {a^m b^n a^p : 2n = m + p} [duplicate]

what's the grammar of the following Language : L = {a^m b^n a^p : 2n = m + p}
new c learner's user avatar
2 votes
1 answer
107 views

Is matching pairs sufficient?

This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is that, why should we check triples (3-element substrings)? Why not ...
PranksterSabeleye's user avatar
2 votes
0 answers
44 views

Finite state automaton

Recently, I have been trying to understand Kitaev's textbook Classical and Quantum Computation, in which he defines a (finite-state) automaton as a function $D:Q\times A'\to Q\times A''$ where $Q$ is ...
Andrew Yuan's user avatar
0 votes
0 answers
30 views

Proving that $ \{0^i10^i\mid i\geqslant 1\}$ is non-regular, using only closure results and the fact that $\{a^nb^n\mid n\geqslant 0\}$ is non-regular [duplicate]

I've been thinking about this problem for several hours, but I couldn't complete the proof. here is what I did: suppose $L'$ is regular ($L' = \{0^i 1 2^i\mid i \geqslant 0\}$). we define the ...
Ali's user avatar
  • 1
0 votes
0 answers
48 views

DFA for $\{s\mid ss\in L(A)\}$ [duplicate]

I've started learning automata recently, and am struggling to figure out how to find a finite automaton that satisfies the following: Given DFA $A_1 = (Q, \Sigma, \delta, q_0, F)$, find a finite ...
Daniel's user avatar
  • 1
4 votes
1 answer
705 views

Are there infinite state machines, and how do their computational power relate to turing machines?

From the internet: ...
JobHunter69's user avatar
1 vote
1 answer
43 views

How to motivate freshman students towards automatic groups?

I'm a new professor and working at a computer science college. I'm going to be responsible for giving a one-hour lecture to motivate my students to study automatic groups. I'm very experienced as a ...
Felipe's user avatar
  • 111
0 votes
0 answers
22 views

How to motivate freshman students towards automata groups? [duplicate]

I'm a new professor and working at a computer science college. I'm going to be responsible for giving a one-hour lecture to motivate my students to study automata groups. I'm very experienced as a ...
Felipe's user avatar
  • 111
1 vote
3 answers
82 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 ...
Mocak's user avatar
  • 15
1 vote
2 answers
66 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 ...
Daniel's user avatar
  • 47
0 votes
0 answers
43 views

PDA equivalent to an $\varepsilon$-free PDA

Say that a PDA is $\varepsilon$-free if it contains no $\varepsilon$ transitions (that is to say, $\varepsilon$ is not in the recognized string symbols even if it still is a stack symbol), but it may ...
Addem's user avatar
  • 347
0 votes
1 answer
62 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 ...
Green's user avatar
  • 11
0 votes
0 answers
36 views

How to determine class of formal language in Chomsky Hierachy

I recently started learning about the chomsky hierarchy and I am preparing myself for an upcoming exam. Often there are tasks to specify the smallest classification of a given formal language. How ...
smallfish's user avatar
0 votes
1 answer
45 views

Lambda Calculus vs Turing Machine

How functional programming using lambda calculus is analogous to construction of Turing machine as per computational aspects?
soham singh's user avatar
2 votes
1 answer
54 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 ...
Ben's user avatar
  • 21
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?
osdinuto's user avatar
3 votes
1 answer
166 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 ...
identicon's user avatar
0 votes
1 answer
31 views

Pumping Lemma Contrapositive, why is this proof wrong?

I have this proof trying to show L={0}^* {1}^* is not a regular language, I know that L is regular but I don't know what in this proof is wrong. If y contains a 0 and 1 and is pumped wouldn't that ...
user167205's user avatar
0 votes
1 answer
72 views

How to put the given context-free grammar into Chomsky Normal Form?

I have questions about how to put the grammar below in CNF - Chomsky Normal Form: S ->aAa | bBb | ВВ; A -> C; B -> S | A; C -> S | ε; I did it like this: I eliminated empty productions: ...
Crow G. F.'s user avatar
3 votes
1 answer
313 views

Repeated rules with more than three symbols for conversion to Chomskys Normal Form

I am trying to convert the below context-free grammar into Chomsky Normal Form, specifically, removing rules that have three or more variables or terminators. $$S \to A a B \;\vert\; B b C$$ $$A \to A ...
pleaseandthankyou's user avatar
1 vote
1 answer
58 views

Not understanding example of a Pushdown Automata

The first example of a (nondeterministic) pushdown automata given in Linz' An Introduction to Formal Languages and Automata is the following: Example 7.2: consider $Q = \{q_0,q_1,q_2,q_3\}$, $\Sigma =...
Sam's user avatar
  • 143
1 vote
1 answer
52 views

Why the Chomsky Hierarchy?

The hierarchy $$\text{regular languages $\subset$ deterministic context-free languages $\subset$ context-free languages $\subset$ context-sensitive languages $\subset$ recursively enumerable ...
Sam's user avatar
  • 143
0 votes
1 answer
43 views

Is the Given Languages CFL or DCFL?

$L_1$ = {$a^nb^mc^xd^y$|$n=m$ or $x=y$} $L_2$ = {$a^nb^xc^md^y$|$n=m$ or $x=y$} For $L_1$: Push a's Now pop the same number of b's , Given n=m If Stack is empty and x=y=0 accept the Langauge else ...
Vedant Khandelwal's user avatar
0 votes
1 answer
127 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 ...
Amir's user avatar
  • 3
-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 ...
Elijah's user avatar
  • 1
2 votes
1 answer
59 views

Is the language accepted by a DFA with a fixed word on the stack after consuming it a deterministic context free language?

Let $\cal M$ be a deterministic stack automaton ${\cal M } = (Q, \Sigma, \Gamma, \delta, q_0, F, Z_0 )$. Let $\gamma \in \Gamma^* $ a word on the stack alphabet. Is it true that the language $$L = \{ ...
hedphelym's user avatar
  • 125
2 votes
1 answer
101 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 ...
Weier's user avatar
  • 231
2 votes
1 answer
71 views

Question about ALL-NFA in PSPACE

Here is the explanation in Sipser's. For step 3, why should we accept only when none of the markers lie on an accept state? If the alphabet of the language is $\Sigma = \{a,b,c\}$, and after the first ...
Bryzem's user avatar
  • 21
0 votes
1 answer
33 views

How to check whether a given language is decidable when the definition contains some predetermined machine

Let $L = \{\langle M, W \rangle \mid M $ is a Turing machine, w is a string and some Turing Machine $M_1$ exists such that w does not belong to $L(M) \cap L(M_1)\}$ I am unsure of how to deal with ...
Aditya 's user avatar
  • 123
0 votes
1 answer
42 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 ...
CSStudent's user avatar
-3 votes
2 answers
58 views

Contradiction via pumping lemma

So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ...
user avatar
0 votes
0 answers
54 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?
user164486's user avatar
0 votes
1 answer
57 views

Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL

I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far. Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
Addem's user avatar
  • 347
0 votes
1 answer
271 views

Is L={0^n 1^n ∣n≥0} context free language?

I looked through many sources which give this as an example for cfl. It also makes sense according to this: But it fails the pumping lemma test. Let's take n=5. According to the Pumping Lemma, we can ...
Aum Thakkar's user avatar
2 votes
1 answer
87 views

Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$

From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the ...
codeing_monkey's user avatar
0 votes
2 answers
117 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 ...
Vedant Khandelwal's user avatar
0 votes
0 answers
23 views

If we have two TMs D1 and D2 and the languages of the TMs L(D1) != L(D2), then is this problem decidable/recognizable? [duplicate]

We know that in the case where, L(D1) = L(D2), the problem is undecidable. But what happens when the languages are not equal? I would assume it's still undecidable, but is it recognizable? And how ...
Luis Ramirez's user avatar
0 votes
0 answers
43 views

What is the difference between abstract machines and automata?

What is the difference between abstract machines and automata? Looking at the respective Wikipedia pages, only automata has a rigorous (mathematical) definition – abstract machines does not. And I can'...
The Pointer's user avatar
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$ ...
Daniel Donnelly's user avatar
-1 votes
1 answer
141 views

Write a CFG for a language of the form L_1 ={a^ib^jc^kd^m|i,j,k>=0, i +j +k> m}

I'm currently having trouble coming with context free grammar to describe this language. My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character ...
bipartite's user avatar
0 votes
1 answer
110 views

Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?

So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be ...
Crypton99's user avatar
0 votes
0 answers
54 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 ...
There's user avatar
  • 111
1 vote
1 answer
45 views

How to formally show computational equivalence or universality using encodings?

I want to formally show that a computational system $\mathcal M$ is computationally universal by showing it is computationally equivalent to some already known universal system, i.e. some UTM. To show ...
Yannik Eik's user avatar
0 votes
0 answers
58 views

How to convert a NFA to alternating finite automata AFA?

I am trying to construct an AFA from a NFA, how do I know if a state of NFA becoms existential or universal in the AFA?
Lea's user avatar
  • 1
0 votes
1 answer
62 views

Regular expression for binary string containing no instances of 01

In order to enumerate such a regular expression, it's clear one can break down the language into the set $s =\{00,01,10,11\}$ and it is clear that we need to enumerate some expression that avoids the ...
bipartite's user avatar

1
2 3 4 5
36