Stack Exchange Network

Stack Exchange network consists of 175 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

Questions tagged [automata]

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

1
vote
1answer
19 views

DFA construction - How to construct an automaton that contains either 0 or 1 occurrences of 010?

I can't seem to make it work. I think I managed to produce a solution when it's exactly one occurrence of 010 but not when it's at most one occurrence. Check out my automaton.
-1
votes
1answer
19 views

regular language proof

Question: Prove that a finite language is a regular language. How would I go about solving this? I tried my own approach (below) but didn't get far because I don't understand how I am supposed to ...
0
votes
1answer
24 views

DFM accepting sum of ab* and ba*

I have a problem with task: Draw a diagram of the deterministic finite state machine accepting the sum of languages marked with regular expressions ab* and ba*. I resolve task: Draw a diagram of the ...
2
votes
1answer
97 views

Gcd is a Regular Language

Show that GCD = {z|z = gcd(x,y), where x, y are binary numbers} is a regular language. [Hint: There is an algorithm that deals with 0s and 1s for this problem.]
0
votes
1answer
27 views

Does the empty string share properties of both zero and $\emptyset$?

I'm confused by the use of the empty string as the author uses it below. This is a excerpt from Introduction to the Theory of Computation by Sipser. Regarding the emptystring line, is this how ...
0
votes
0answers
22 views

DFM ab* and ba*

Draw a diagram of the deterministic state finite machine accepting the concatenation languages marked with the regular expression ab* and ba*. How should I draw this diagram? Can you help me ? Best ...
1
vote
1answer
31 views

DFM symbol a occurs twice

Let the L language over the alphabet {a, b, c} consist exactly of all words in which the symbol a occurs at least twice. Draw a diagram of the deteminist state-finite automaton accepting L and provide ...
1
vote
0answers
21 views

Open problems in Cellular Automata field

here there is a link on Wolfram about 20 open problems of CA theory. Has anyone of them been solved or tested? I'm searching for literature.
2
votes
2answers
48 views

context free language prove or disprove

I have to prove or disprove that for every language $L$ which has the properties: for every non-prime length there is at least one word in L. for every prime length none of the words are in L. is ...
0
votes
1answer
33 views

Give a state diagram for an NFA whose language L = …

L = {w ∈ {0,1,2} *: w is a ternary representation of an integer that is a multiple of 3 but not a multiple of 9} I've written a DFA accepting multiples of 3, but I'm not sure how I should proceed. ...
-1
votes
1answer
37 views

Create NFA where the second symbol of the string is the same with the last symbol

I have try Let $L= \{a,b,c,d, \dots, z\}$. Create NFA where the second symbol of the string is the same with the last symbol. How do I solve this? Should I do repeatedly until z?
-2
votes
0answers
30 views

How to prove that regular languages are closed under an operation

How to show that regular languages are closed under the operation $C$ defined as follows $$ C(B_1, B_2) = \{w \in A^* \mid \text{ there exists } x \in B_2 \text{ such that } wx \in B_1 \} $$ I was ...
1
vote
1answer
22 views

If a language and its complement are context-free, is it regular?

If both $L$ and $\overline{L}$ are context-free, is $L$ necessarily regular?
1
vote
1answer
36 views

Language of this finite state automaton?

What would be the formal definition of the language for the following Finite State Automaton?
0
votes
1answer
59 views

Design DFA to check even number of 1s using 2 states.

The alphabet is {0,1}. Zero 1s in the string should be rejected. This can be done easily using 3 states. Can this be done usinng 2 states?
1
vote
2answers
31 views

Try finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R [duplicate]

"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.
1
vote
0answers
54 views

Finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R [duplicate]

Finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R i am looking for the simplest solution- using a known languages that do not demand another formal proof.
1
vote
1answer
41 views

Finding languages such that $L_1\subset L_2\subset L_3$ where $L_1,L_3\notin$ RE and $L_2\in$ R [duplicate]

I am struggling to find such languages $L_1$, $L_2$, and $L_3$ such that $L_1\subset L_2\subset L_3$ where $L_1,L_3\notin$ RE and $L_2\in$ R. I know they exist, I need help finding them.
0
votes
1answer
56 views

Finding languages such that $L_{1} \subseteq L_{2} \subseteq L_{3}$ where $L_{1}, L_{3} \notin \mathbb{R}$, $L_{2} \in \mathbb{R}$

I am struggling to find such languages $L_{1}$, $L_{2}$, and $L_{3}$ such that $$ L_{1} \subseteq L_{2} \subseteq L_{3} $$ where $L_{1}, L_{3} \notin \mathbb{R}$ and $L_{2} \in \mathbb{R}$. I know ...
4
votes
1answer
90 views

Turing machine with read only part and finite tape

Given a Turing machine whose input part is read only , and in addition to the input part has a finite tape of length K, prove that this is equivalent to a DFA. I tried to find some bound for the ...
0
votes
0answers
53 views

Need a PDA for L={ a^n b^m c^m d^n n,m>=1 }

I am trying to desing a PDA for automata lecture.Language is L={ a^n b^m c^m d^n n,m>=1 } ...
1
vote
1answer
130 views

What is the source of formal descriptions for large uncomputable ordinals clockable by Infinite Time Turing Machines?

I can imagine the process of analyzing the computation of an ITTM at any limit stage denoted by $\alpha$ if $\alpha$ is a computable ordinal: basically, we take the description of some standard Turing ...
2
votes
2answers
82 views

Given a transition table do digraph, determine if it is DFA or NFA and build grammar

For the next transition table: $$\begin{array}{|c|c|c|c|}\hline&0&1&2\\\hline a&a&b&d\\\hline b&a&b&c\\\hline c&c&d&a\\\hline d&c&c&a\\\...
0
votes
1answer
30 views

Is $L_4$ a CFL?

Consider the following language: $$L_4 = \{a^ib^jc^kd^l : i,j,k,l \ge0 \wedge i=1 \Rightarrow j=k=l\}.$$ Prove or disprove: $L_4$ is a context-free language. To me, it looks like $L_4$ can be ...
0
votes
1answer
41 views

Prove that the grammar defines language

Given grammar G, I have to prove it defines the language of all words which are not palindromes. In other words, $w\in L(G) \Leftrightarrow w\in L $ where $L =$ {w$\in$ $\sum^*$ | w is not palindrom} ...
1
vote
1answer
34 views

how to prove that L is not context free

Given $\sum_2$ = {$\begin{bmatrix} 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$,$\begin{bmatrix} 1 \\ 0 \end{bmatrix}$,$\begin{bmatrix} 1 \\ 1\end{bmatrix}$} , and a language $L$ = {$...
1
vote
0answers
36 views

How to guess the end of pushdown automata by emptying the stack?

Let language $L=\{\sigma_1w_1c\sigma_2w_2c...\sigma_nw_nc\}$ where: $$ 1\le n\\ \sigma_i\in \{a,b\}\\ w_i\in \{a,b\}^+\\ \exists i:i\le|w_i| $$ and at least one condition from the two conditions ...
0
votes
0answers
16 views

Concatenation of transition system

I do not understand how can I make the concatenation of transition system with $P_{\text{safe}}$ in question c). In the first question (a) why I have as feedback $\lnot c$ a from the third state to ...
0
votes
1answer
50 views

Convert this grammar to language

I want to convert the following grammar to language but I am not able to think and answer. $$S \to aSa \mid bSa \mid ab \mid ba$$ It gives me a lot of choices when I tried building its derivation ...
0
votes
1answer
32 views

building a DFA from equivalence classes of $R_L$(tricky)

i've encoutered an interesting question from an old exam with no solution and i was wondering: how do you build a dfa(deterministic finite automata) from given equivalence classes? this is the ...
0
votes
0answers
29 views

finding equivalence classes of $R_L$ in automata(Nerode)

i am having trouble understanding this concept. would really appreciate your corrections so i could learn and improve. 1)$L=\left\{w\:\in \Sigma^* |\:w\:begins\:and\:ends\:with\:aa\right\}$ 2)$L=\...
0
votes
1answer
57 views

which of the following languages over $\Sigma \{0,1,\$\}$ are regular?

i saw this nice exercise in some old summary and i was wondering if i got it correctly. basically i have to decide whether a language is regular or not and give a short explanation. (languages over $\...
0
votes
1answer
35 views

proving that $a^6 \in L$ (tricky) (pumping lemma)

i've encountered a quite tricky question that i don't understand, and would appreciate your help with: it is said that by the pumping lemma, for a certain L there exists(guarenteed) n=2. also known ...
0
votes
0answers
23 views

NFA to Regular expression

Above is a try of converting a NFA to a regular expression (can a moderator rotate it please). There must be somewhere along the process where I do something wrong because if you compare the end ...
0
votes
0answers
10 views

When does the initial state lead to empty string when converting a DFA to context-free grammar?

I saw several examples of converting DFA to context-free grammar. Sometimes the grammar output includes the production rule such that the initial state $S$ leads to empty string: $S\to\epsilon$, ...
1
vote
1answer
38 views

How can I prove given language is not regular?

My first post here, so glad I found this great place. Hoping I could improve and learn a lot from you and contribute in the future if I can. I have a problem with the following scenario: Given $\...
4
votes
1answer
176 views

How many Nerode equivalence classes does the language $x\neq y$ have?

I have a language $L_k$ over the alphabet $\Sigma=\{0,1,\#\}$ defined as follows: \begin{equation} L_k=\{x\#y|x\in\{0,1\}^k,y\in \{0,1\}^*\wedge x\neq y\} \end{equation} I would like to find all the ...
4
votes
1answer
42 views

Regular Expression From a DFA

I am trying to create a finite automate that would accept any strings that have at least to 0s but reject all strings that have consecutive 0s. I have designed a deterministic finite automaton (DFA) ...
0
votes
1answer
57 views

Given a regular language L, prove or disprove L' is regular

Given $NFA$ $N$ , $L(N)$ regular language and two words $w1$,$w2$ $\in$ $\sum^*$ such that $w1$ $\neq$ $w2$. I have to prove or disprove that $L'=$ {$z\in \sum^*|\exists$ $w1,w2$ :$w1z$ $\in$ $L(N)$ ...
0
votes
0answers
50 views

build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

I think it's similiar to NFAs. I replace the finite states of the given automaton for start-states for my new automaton. I do it with $\epsilon$-transition from the start state to the actual finite ...
0
votes
0answers
293 views

Automata theory - How many Nerode equivalent classes for language $L_k$ [duplicate]

Given a constant $k$ we will define the language: $$L_k =\{x\#y \mid x \in \{0,1\}^k, y \in \{0,1\}^* \text{ and } x \not=y\}$$ How many Nerode equivalent class does $L_k$ have? I need to show ...
0
votes
1answer
49 views

Left Linear Grammer to Right Linear Grammer

I am learning Regular Grammar and given the problem to convert S->S10/0 from left linear to right linear grammar. I've seen examples of such conversions where we first write the reverse ...
2
votes
1answer
45 views

Proof for minimum number of states for a epsilon free NFA is $2^n$

I have the following question which I could not proceed: Let $$L=\{w \in \Sigma^* \mid \text{all symbols of the alphabet occur even times in } w\}. $$ Prove that any NFA accepting $L$ requires $2^...
0
votes
1answer
409 views

Conversion of an Epsilon NFA to a DFA

I need to convert this NFA to a DFA, but I only have the method for NFAs without Epsilons: My calculation was: But the expected result is: Is there a process to use for converting this to get the ...
3
votes
2answers
199 views

prove or disprove if the following language is regular language

for $A,B\subseteq\{0,1\}^*$ regular languages prove or disprove that $L_2$ is a regular language: $L_2 = \{x \in A | \exists y \in B : |x|_1 =|y|_1 \}$ $|x|_1$ means the number of appearances of 1 ...
0
votes
1answer
23 views

How to connect DFA state which had no transitions after minimizing it?

I have the following DFA, let it be $A$: The problem asks to find the minimal connected DFA for $A$, it is as follows according to the solution (the state $\{d,e\}$ is called $e$ for simplicity's ...
1
vote
1answer
29 views

How to find a DFA for combinations of even and odd occurrences $0,1$?

Let $L$ be a language over $\{0,1\}$ whose Nerode equivalence classes are: $$ \{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=0\}\\ \{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=1\}\\ \{w|\#_0(w)\...
0
votes
1answer
37 views

How to find equivalence classes for $R_L$ for the language of words that begin and end with $aa$?

Let $R_L$ be a relation such that: $xR_Ly \iff \forall z\in \sum^*:xz\in L \iff yz \in L$. Find the equivalence classes for $R_L$ for this language: $$ L=\bigg\{w\in \sum^*\bigg| w\quad \text{starts ...
1
vote
1answer
52 views

PDA: Symbol in first half

How do I construct a PDA where: $L = \{w \in \{0, 1\} ∗ : |w| \text{ is even and } w \text{ contains at least one 1-Symbol in the first Half}\}$ To me it seems impossible to know when I reached the ...
1
vote
1answer
35 views

'$L$ almost' is regular

Given a regular language $L$, I have to prove that '$L$ almost' is regular where '$L$ almost' is all the words which differ from the words of $L$ by one char. for example, if $L = \{aab,aaa\}$, so $...