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.
0
votes
1answer
48 views
What are the axioms of automata theory?
Every theory has axioms and theorems derived from axioms.
How many axioms are there for automata theory? What are the axioms of automata theory?
0
votes
0answers
37 views
Minimization of DFA 3 inputs Table Filling Method
I do understand how minimization of DFA works where there are 2 words lets say $\{a, b\}$. However, I came across this minimization of a DFA over the language of $\{a, b, c\}$ $\left(\Sigma, \{q_0, ...
1
vote
1answer
37 views
Language of all sequences of permutations whose product is the identity
Let $\Sigma$ be the set of all permutations in $S_n$. What is the minimum number of states in a DFA accepting the language of all words over $\Sigma$ which multiply to the identity permutation?
For ...
5
votes
4answers
2k views
Is the infinite language unrecognizable in a Turing machine?
This question is building up on an older one, here.
But now let's say we keep $Σ=\{0,1\}$. Is the TM that accept anys ($1^x \mid x \gt 0$) recognizable?
That means 1, 11, 11111, 1111111, and so on ...
1
vote
1answer
30 views
Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b [duplicate]
How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \{a, b\}$, defined by the strings $w$, such that $|w|_a = |w|_b$?
I'm sorry I can't give any approach of what ...
3
votes
2answers
43 views
Regular expression for binary words with 1 in the middle
Given the alphabet $\{0,1\}$, generate a regular expression with the following language: $$ \{w\in \Sigma^* \mid w \text{ has odd length and its middle symbol is }1\}. $$
I'm having trouble finding a ...
-5
votes
0answers
19 views
Should we still study finite automatan? [duplicate]
Can anybody help me with this homework question?
In the era of information, technology changes at drastic speed, and the same is observed in Computer Science and Information Technology. The need ...
2
votes
2answers
39 views
Is the reverse of a closed under operation maintainable?
I'm looking at the following question from this handout:
The class of decidable languages is closed under union
My question is, does this hold in reverse? Is there a phrase for this?
Basically, if ...
0
votes
0answers
12 views
How to find equivalence classes for a regular language? [duplicate]
I was wondering if there is a formal approach to find equivalence classes for a regular language.
My guess:
Construct a minimal DFA based on given regular language.
Based on states in DFA, we can ...
1
vote
1answer
15 views
What does it mean to take a union of a transition function with a starting state?
$$
\delta(q,a) = \begin{cases}
\delta_1(q,a) & q \notin F_1 \text{ or } a \neq \lambda \\
\delta_1(q,a) \cup \{q_1\} & q \in F_1 \text{ and } a = \lambda.
\end{cases}
$$
Look at the second ...
1
vote
0answers
26 views
Determining whether Turing machine halts on input: primitive recursive?
In Elements of the Theory of Computation by Lewis and Papadimitriou, the authors use a specific function for proving that application of unbounded minimization on a primitive recursive function need ...
1
vote
1answer
19 views
NPDA transitions to different states by taking same input and popping same top element of a stack
Suppose i have some NPDA and there is some transition functions defined as:
$\delta(q_{1},a,A) = (q_{2}, A)$
$\delta(q_{1},a,A) = (q_{3}, Z)$
Is it allowed?
I understand, that since the NPDA is ...
1
vote
1answer
38 views
How to create a cellular automata rule to achieve a desired pattern?
Normally, to find the rule that is suitable to our need, we have to generate all possible rules and apply each rule on a seed and check whether a rule produces a desired pattern. This method is ...
0
votes
1answer
36 views
Maximum number of words in deterministic finished automata with k-states [closed]
I have exercise:
We have a given finished deterministic automata. It has 5 states and is
based on the alphabet {a, b, c}. It can create n different words (we assume that n <
inf). What maximum ...
1
vote
1answer
26 views
Prefix/suffix property of language containing only empty word
Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property?
The definition says that language has prefix/suffix property requires that there is no code word in the ...
0
votes
0answers
14 views
Show that every regular language is represented by some regular expression in disjunctive [duplicate]
A regular expression is in disjunctive normal form (DNF for short) if it is of the form
α1 ∪α2 ∪ · · · ∪αn for some n ≥ 1, where none of the terms αi contains an occurrence of ∪.
Show that every ...
7
votes
0answers
75 views
Automata that is Turing complete if you add a nondeterminism
Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for ...
1
vote
1answer
35 views
How to build a finite automaton for right quotient of a regular language?
Let $L$ be a regular language over $\Sigma=\{a,b,c\}$. Build a finite automaton for $L/\{a\}$.
Because $L$ is regular then a DFA exists for it: $A=(\Sigma, Q, q_0, F, \delta)$.
Let $M$ be a finite ...
1
vote
1answer
39 views
If a deterministic finite automaton recognizes a language, must that language contain every accepting input?
May a DFA recognize a language which is a proper subset of the set of all accepted inputs?
For instance, if there is a DFA which decides if an input $W$ has $w_0 = w_n$, can it recognize a language $...
0
votes
0answers
19 views
What is “Phrase structure grammar”?
I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar:
Type-0 grammars generate recursively enumerable languages. The
...
0
votes
0answers
10 views
NFA to DFA with Epsilon transition [duplicate]
Does my first following of the NFA-DFA Algo look correct? The two tables are me following the algorithm to convert...
And for the second problem how do I deal with epsilon transition while following ...
0
votes
1answer
29 views
Does left factoring CFG make it unambiguous?
I came across following problem:
If the CFG is left factored then it must be Unambiguous and Not left Recursive.
TRUE/FALSE?
I have many thoughts about this. But I feel they are somewhat ...
0
votes
1answer
38 views
Why are finite automata defined as ordered $n-tuples$ and not as sets?
First off, I should mention that I am a new contributor on this site and as such, please bear with me if this has been asked and answered before. I searched to the best of my ability to find similar ...
1
vote
3answers
74 views
Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2
Given is an alphabet $\Sigma = \{ a, b, c \}$, and a language $A4 =\{ w \mid w \in \Sigma^* \wedge |w|_a \operatorname{mod} 2 \ge |w|_b \operatorname{mod} 2 \}$
whereas $|w|_a$ is the number $a$'s in ...
0
votes
1answer
22 views
How to generate a grammer from this language? [duplicate]
I'm trying to generate a grammar from this language:
L={a^i b^j c^k d^l : i+j=k+l}
to be clear its a in the power of i and b in the power of j... and so on, so ...
0
votes
1answer
52 views
Ambiguous grammar to equivalent unambiguous grammar
I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous.
Given the ambiguous CFG :
$S \to A\mid B$
$A \to aAb\mid ab$
$B \to abB\mid \epsilon$
My ...
1
vote
1answer
39 views
Constructing a pushdown automaton that accepts L*
Would appreciate if you could take a look at what I did and help me finish it.
Given a pushdown automaton that accepts a language $L$ by final state, construct a pushdown automaton that accepts $L^*...
1
vote
1answer
31 views
is $0^x1^y$ context-free?
given that L is regular, does the following make a context-free language?:
i) $\{0^x1^y \mid 0^{x+y} \in L\}$
ii) $\{0^x1^y \mid 0^{x-y} \in L\}$
since L is regular, i presumed that i) can be put ...
1
vote
1answer
39 views
Intersection of two incomplete DFAs
Let assume that I have the following two automata A1 and A2 :
I have to do the intersection of the two, so I did this :
My question is related to the "∅". If I have two incomplete automata without ...
0
votes
0answers
25 views
What is abstract machine for parallel multiple context free grammar (PMCFG)?
It is said, that PMCFG (Parallel multiple context free grammar) http://www.aclweb.org/anthology/P93-1018 is mildly context-sensitive grammar. My question is - what abstract machine can be used for ...
0
votes
0answers
21 views
How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]
I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
0
votes
1answer
50 views
Regular expression or automata for language with odd number of 0's and odd number of 1's
Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
0
votes
1answer
40 views
What is the set of languages accepted by empty stack pda?
I am having a confusion. Empty stack pda will always accept episilon. Therefore a language not accepting episilon will still be accept episilon, so how can we avoid this?
2
votes
1answer
36 views
finding separating words (Nerode)
i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me ...
5
votes
2answers
228 views
Constructive proof to show the quotient of two regular languages is regular
I have a question regarding the quotient of two regular languages, $R$ and $L$.
I saw the answers to this question: are regular languages closed under division
and the proof sketch is not ...
2
votes
2answers
55 views
How to prove certain parts of one regular language restricted by another regular language is also regular?
I’ve encountered the following difficult question that I don’t know how to solve.
$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...
0
votes
0answers
41 views
How to design synchronisation algorithm to combine two automata?
I have two automata of states, transition and events (Etat, Transition, evenements) and I want to create a function that create the synchronized product between those two automata. For instance, given ...
0
votes
1answer
31 views
Nondeterministic automaton accepting only words whose first letter is identical to their next to last letter
I was asked this question and could not come to the correct answer:
Let $L$ be the language of all words over $\{a,b\}$ where the first letter is identical to the letter that is next to last. (Pay ...
0
votes
1answer
39 views
Which one of the following string is DCFL
Is odd length pallindrome DCFL or NCFL?
Like
1) $L=\{w1w^R\mid w \in \{0, 1\}^*\}$
or
2) $S\rightarrow aSa\mid bSb\mid a$
or
Suppose odd length String like
3)$S\rightarrow aSa\mid bSb\mid aSb\...
-1
votes
3answers
86 views
why can not NPDA is equal to DPDA?
I have recently read that turing machine can be remodeled to perform as PDA now, i have a question that since DTM = NDTM ( non deterministic Turing machine) then every DTM can remodeled to be NDTM ...
0
votes
0answers
22 views
Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#…#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]
Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
0
votes
0answers
18 views
contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2} [duplicate]
Is this language contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2}. I think it's not but can't prove it.
0
votes
1answer
39 views
What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?
I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking ...
5
votes
2answers
144 views
Why do DFAs with a single final state have less power?
I came across this question in a test and I had to answer whether it is true or false.
DFA with single final state has the same powers as DFA with more than one final state.
I was confused by what ...
2
votes
2answers
80 views
Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L
I'm having trouble with proving the following, and my attempt and confusion is mentioned further below.
PROBLEM STATEMENT:
For a string $w = a_1 a_2 a_3 a_4 a_5 a_6 a_7 \dots$, define $third(w) = ...
4
votes
1answer
52 views
Does the following operation makes the language regular? [duplicate]
I came across a question stated as $L = \{wxwy \mid w \in \{0,1\}^* , x,y \in\{ 0,1\}^* \}$ is regular and I have no problem understanding it.
However I thought what could happen if the language is ...
0
votes
1answer
22 views
Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.
...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM.
I had this problem on my exam. From my ...
0
votes
1answer
21 views
Counterexample for simple parity automaton reduction
I am dealing with deterministic parity automata and state space reduction (not minimization).
If we define $\equiv_L$ to be the equivalence relation that sets two states equal iff starting from those ...
1
vote
1answer
24 views
is it possible to know if a language is regular if its equivalence classes are finite?
i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.
1)suppose we have some language L over $\Sigma$, can we know if L is regular ...
2
votes
1answer
36 views
Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language
For regular languages $A,B\subseteq\{0,1\}^*$, is
$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$
regular, where $|x|_1$ means the number of appearances of 1 in the word $x$?
i need to ...
