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.
1,311
questions
0
votes
1answer
27 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 ...
-2
votes
0answers
27 views
I need help in creating deterministic finite automata
Let Σ = {a, b, c}.
Draw a DFA that rejects all words for which the last two letters match.
Draw a DFA that rejects all words for which the first two letters match.
1
vote
0answers
21 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
36 views
Prove that regular languages are closed under Kleene star
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
21 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
50 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
53 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 ...
3
votes
1answer
68 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
31 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
37 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
38 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
29 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 ...
0
votes
0answers
19 views
Constructing a PDA which acceptsL {${a^i b^j c^k}$| $i,j,k≥0$ and $i=j$ or $i=k$}
I have to construct a PDA which accepts the L {${a^i b^j c^k}$| $i,j,k≥0$ and $i=j$ or $i=k$}
I cannot quite graph how to handle the 'or'
To make it easier for myself, I constructed strings where $i=...
-2
votes
0answers
24 views
Right-linear and left -linear Grammar
Could some explain what's the difference between right-linear grammar and left-linear grammar?
Maybe on this example:
$L:=\left\{w \in\{a, b\}^{*} | w \text { does not contain the subword abaab }\...
1
vote
1answer
52 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
0answers
35 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
26 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 ...
0
votes
2answers
78 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
39 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
93 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
68 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.
1
vote
1answer
37 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
154 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
80 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
31 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
27 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
121 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
38 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
26 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
42 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
37 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
32 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
158 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
57 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
5k 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
50 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
61 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
85 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
70 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
29 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 ...
0
votes
1answer
47 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
172 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
0answers
24 views
Is it decidable whether Turing Machine never scans any tape cell more than once when started with given string
The problem:
Is it decidable that the set of pairs $(M,w)$ such that TM $M$, started with input $w$, never scans any tape cell more than once.
How can I easily prove above to be decidable. I found ...
0
votes
2answers
65 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
43 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 ...
2
votes
1answer
125 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
63 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
59 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
41 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
$\...
