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
2
votes
0answers
42 views

can a DFA with only final states be minimized?

I need to construct a DFA for a certain language with as little states as possible. so far my "best" solution contains 15 states. however, people claim it is doable in 7 states only. I tried for ...
0
votes
1answer
44 views

Closure on regular languages

A) Let $L$ be a regular language. according to the theorem there is an DFA which accepts the language. Describe shortly how to change the DFA to NFA which Accepts $L^R$, where R is reverse. There is ...
1
vote
1answer
46 views

Converting this NFA-e to DFA

I came across this question about NFA-e and thought to convert it into DFA: This is what I did. $\begin{array}{|c|c|} \hline & a \\ \hline q_1&q_2 \\ \hline q_2&\phi \\ \hline q_3&...
0
votes
0answers
44 views

Prove that regular languages are closed under Kleene star [duplicate]

Given $L$ is a regular language, how can I prove that $L^*$ is a regular language too? I've constructed an NFA which contains a new initial state that has an $\epsilon$-transition to the original ...
0
votes
1answer
32 views

Context-free grammar for language involving multiplication

I'm struggling to find the context-free grammar for the following language: $$ L = \{a^sb^tc^m:s,t,m\in\mathbb{N}^+\land1\leq t\leq3\land s\times t=m\} $$ Any help would be appreciated.
0
votes
1answer
58 views

Are there more languages than functions?

My gut says "no", but I don't know why. For any function $f$ over strings on an alphabet, one can define a language in which every word is just the concatenation of a string $s$, a delimiter, and $f(...
1
vote
2answers
277 views

Prove the following language is regular?

Assume $L_1$ is a regular language, and define: $$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$ Show that $L$ is regular. I first tried to prove by showing that the ...
3
votes
1answer
87 views

Can one determinize finite automata over infinite trees?

I'm currently considering deterministic, nondeterministic, universal, and alternating automata over infinite words and trees, with Büchi, co-Büchi, Muller, Rabin, Streett, or parity acceptance ...
1
vote
2answers
337 views

Proving a language is not regular using Myhill Nerode Theorem

Let $L = \{\alpha\in\{a,b,c\}^{*} \mid \alpha \text{ is palindrome}\}$, show that $L$ is not regular using Myhill-Nerode relation. I don't know how to show that $L$ has infinite equivalence classes ...
-1
votes
1answer
105 views

Design a DFA recognising the following language

Design a DFA over alphabet (a,b) such that for all it's string no prefix contain two more a's than b's and two more b's than a's and the number of a's is equal to b's. Is it possible to design a DFA ...
-2
votes
1answer
170 views

Design a DFA for the language L = {w | w contain 2 a’s at any position and greater than 3 b’s at any position, w ϵ {a.b}*}/

I do not understand this question,because for saving Number of a's and b's memory is required,which FA does not provide.could anybody please explain this?
1
vote
0answers
56 views

A state space for river crossing puzzle

I am solving the river crossing puzzle with 6 participants. You must transfer all the people across the river in this flash game respecting the following rules: The ferry can carry no more than 2 ...
1
vote
1answer
151 views

Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
0
votes
1answer
74 views

NFA-$\epsilon$ extended transition function for inverted strings

It is well known that in $NFA-\epsilon$ the extended transition function is defined as it follows: \begin{align*} \hat\delta: Q &\times \Sigma^* \rightarrow \mathbb{P}(Q) \\ \hat\delta(q,\epsilon) ...
0
votes
0answers
50 views

How to write a regular expression that excludes certain strings? [duplicate]

It's a homework problem. Assume $\Sigma = \{a ,b\}$, I am asked to construct a regular expression that does not have both the substrings bba and abb. My idea was: construct a regex that matches ...
1
vote
3answers
363 views

Large DFA to regex?

For an assignment for one of my courses, one of the questions is to provide a regular expression for the language: "the set of strings such that the number of 0’s is divisible by six, and the number ...
0
votes
0answers
109 views

Minimization of DFA- one state mark or no mark?

I want to know, what if the DFA is merged states. So if my DFA starts with q0 and then have (q0,q1) state it goes to with an 'a' for example. How do I do the table filling method. I tried to rename ...
0
votes
3answers
410 views

Prove that a language is regular

I'm working on an example which says that a string x is obtained from a string w by deleting symbols if it is possible to remove zero or more symbols from w so that just the string x remains. For ...
-1
votes
1answer
81 views

“If A is nonregular, then there exists a nonregular language B such that A ∩ B is finite.”?

Is the statement true? I feel that the statement is true. I want to prove it but I don't know how to start the proof. Any help would be appreciated.
2
votes
1answer
74 views

Is it possible to constract Moore or Mealy machine with a different size of input and output?

Is it possible to constract Moore or Mealy machine to take input tape: 0011 and output: 00001111 (or vice versa). In other words, input and output have different size. I want to construct FSMs to ...
1
vote
2answers
189 views

Why does this NFA having an empty symbol

I'm trying to understand the difference of DFA from NFA I have this example in my coursebook Are the empty symbols at the start necessary? or can we do away with them to have something like this
-1
votes
1answer
115 views

Constructing an NFA for a language defined over $\Sigma = \{0, 1\}$

The language is defined as $$L = \{0^n10^m10^q \mid n,m,q \in \mathbb{N}, q \equiv nm \mod 5\}.$$ Can someone help me get started on this question? I don't know what part of the question I should do ...
1
vote
1answer
59 views

What are HP and MP in this context?

From Kozen's Automata and Computability, 3ed, lecture 32 p. 328: What are HP and MP in this context? I tried looking around and this text says: How did the halting problem and membership problem ...
2
votes
1answer
60 views

The PDA have to finish reading the input?

I have PDA which has final state that accept 'c' char, and there isn't any cross to other state. The input abca will accept, because there is 'c', or the PDA would stuck?
-1
votes
2answers
147 views

Why L' is not regular?

$$L'=\{ww|w\in L\}$$ I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular. How can I give such an example if according to closure ...
1
vote
1answer
56 views

Distinction between 2 languages.One is regular the other is not

whenever it needs to be determined if langage is regular or not, I use the notion that it is impossible for a machine to "remember" an infinte states. given 2 languages:$L_1=\{(01)^{n}(10)^{n}|n \in \...
0
votes
1answer
30 views

Can I assume that L1 is regular?

$L_{4},L_{2}$ are regular languages. given an expression which we know is regular: $L_{4}\cap \bar{L_{2}}\cap \bar{L_{1}}$ May I assume that the language $L_1$ is regular? using closure properties
0
votes
0answers
45 views

Is this proof for pumping lemma legit?

Prove that $L=\{a^{n}b^{m}c^{k}\mid n\leq(m+k)\}$ is not regular. I used the pumping lemma as follow: there exists $n\in \mathbb{N}$ $z=uvw$ $|uv|\leq n , |v|\geq1$ $uv^iw$ is a string in L, so ...
0
votes
1answer
96 views

How do I replace a D Flip Flop with a JK Flip Flop

Hello I have this circuit with this I want to learn about Mealey and Moore. Is this a Mealy Automata? I would say yes because of the upper LED depends on the variables I got. Otherwise isn't the ...
0
votes
0answers
34 views

What unusual property does this finite automata yield?

I'm asked to construct a finite automata for a given task. The Automata should accept the values zero or one. In the starting ...
3
votes
2answers
398 views

If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?

I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack. But, a link of Show that { ...
-1
votes
1answer
73 views

Is a language regular if a word is in a regular language but the reverse is not?

$$A_1 = \{ x \mid x \in A , x^R \not\in B\}$$ $A$ and $B$ are regular over $\Sigma$. Is $A_1$ regular?
15
votes
2answers
6k views

Can a deterministic finite automaton ever go into an infinite loop?

As the title suggests, is this possible? Or does it halt execution when it hits the trap state? Thanks to anyone who can clear this up.
0
votes
1answer
161 views

Pushdown automaton from given code for parsing a while statement

I was preparing for my exam and have some questions that can possibly come on the test. There is a task to make pushdown automata from a given code: ...
0
votes
1answer
39 views

Is every program is equivalent to a Push Down Automata?

so I was reading about stack-organized computer. Does a stack-organized computer implies that every program is equivalent to (and not more powerful than) a Push Down Automata?
1
vote
1answer
77 views

How specifically do I need to describe (in words) the language of a regular expression?

For the regular expression $(a^*ba^*b)^*a^*$, I want to learn how to describe it in words. I know there are an even number of $b$s but how much do I need to explain it? Do I need to explain it enough ...
2
votes
1answer
208 views

How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?

I am struggling to answer the following question: How many different languages over the unary alphabet {a} are recognized by 2-state DFAs? According to the textbook, the hint was to first ...
2
votes
0answers
81 views

Which of these languages is regular? The Pumping Lemma seems to show none are

I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular? $$ \{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
2
votes
1answer
75 views

NFA equality for automata with partial transition functions and all states accepting

Given two nondeterministic finite state automata with partial transition functions, such that all states are accepting, except for the implicit failure sink state, is it possible to decide in ...
1
vote
1answer
57 views

Generate code from automata

I am trying to figure out the process of generating code (set of instructions, implementation language specifics dont matter at this time) from an automaton. The description of my intent is vague ...
1
vote
4answers
507 views

Does infinite length strings lead to uncountable languages?

This answer says: We can have uncountable languages only if we allow words of infinite length. So does that means any (finite / infinite) language or any (finite / infinite) set of languages over ...
0
votes
2answers
83 views

Is it decidable if there exists some input such that the TM makes at least five moves?

I am reading this excerpt from Ullman's book: I have following doubts: (related to red underline) TM can make 5 left moves or 5 right moves. So it will need at max 11 cells. Then how it says 9? (...
0
votes
1answer
58 views

Need help with previous “Automata / Theory Of Computation” exam question

I passed by this question in a previous exam while studying for the "Automata / Theory Of Computation" and I am struggling to find answer. I would appreciate it if someone can help me with it: This ...
3
votes
1answer
633 views

Finding the union, subtraction, and intersection of two DFAs

I recently solved problem of finding union of two DFAs and came up with some observations. I need confirmation about them along with some other facts: I can prepare the union, subtraction and ...
2
votes
1answer
335 views

PSPACE-completeness of DFA intersection problem

Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness. It seems to me that I ...
0
votes
2answers
351 views

When Turing Machine behaves like Finite state automaton

I read following: Turing Machine with finite (fixed sized) tape is essentially Finite state automaton. Is this fact correct? My doubt is Turing Machine can go infinite loop even on finite tape if ...
1
vote
1answer
53 views

Regular Language - Context Free Language

I know this is not a question answer posting site but for the sake of explaining my doubt I will like to post a question Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet $\...
2
votes
1answer
268 views

Prove/disprove: If $𝐿_1$ is a finite language but not empty and $𝐿_2$ is NOT regular then $𝐿_1 \circ 𝐿_2$ is NOT regular

That what I have so far, but I am not sure at all. Assume toward contradiction that $𝐿_1 \circ 𝐿_2$ is regular. Define $\Sigma' = \{\sigma'|\sigma\in\Sigma\} $. Define a regular substitution $\...
3
votes
2answers
134 views

Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet?

Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet? Is this even a meaningful question? For example, if $\Sigma = \{\texttt{0}, \texttt{1}\}$, we can encode any ...
1
vote
2answers
338 views

Is a^mb^n where m=n^2 a CFL?

Is $a^mb^n$ where $m=n^2$ a CFL? I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right? On the other hand I ...

1
3 4
5
6 7
30