# Tagged Questions

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

36 views

### Is there a fast way to know whether a language is regular or not?

Or at least have an idea? Because I can't see whether a language is regular before I can disprove it by pumping lemma and it takes me like a hour to try to disprove.
136 views

### What did the proof by diagonalization actually disprove?

http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fourse5.html I sort of understand the proof, but is it showing that some language are undecidable? If so, what language exactly? Because each ...
260 views

### Backus-Naur Form with automata

Parsers & compilers usually utilize deterministic finite automata to parse input. It's very easy to implement a generic DFA tool, that simulates any DFA table for example to validate input. ...
110 views

### turing machine accept and reject state

I am pretty new to Turing Machines and I am trying to understand the basic things first...so my question is , would this machine accept all words ending in 'a' ? if ...
29 views

75 views

### Pushdown Automata

I having trouble constructing NPDAs for these two languages: $L_1 = \{a^nb^m \mid 2n \le m \le 3n\}$ $L_2 = \{a^nb^mc^k \mid n = m \: or \: m \ne k\}$ Would these be the proper states for the first ...
40 views

### FSM to be regular with atleast two 0's and at most two 1's

Is it possible to construct a FSM to prove that the set $X$ is regular, where $$X = \{s \in \{0,1\}^* \mid \text{s contains at least two 0's and at most two 1's}\}\ ?$$
50 views

### using pumping lemma to prove that a set is not regular

A={s11s|s $\epsilon$ {0}^*} so the strings 00011000 and 000001100000 are accepted of A but not 00100 or 001100000. Demon chooses k. ...
204 views

### Prove this language is not regular [closed]

How do I prove that this language = {1^k | k is a perfect square} is not regular by showing that no DFA can accept the language?
45 views

### Can someone explain me the proof?

I don't really understand the proof and I don't understand why it is M2 that "leads" to a reject state instead of M1.
43 views

### Can someone explain to me how this is a proof?

I honestly don't understand how this proves anything.
50 views

### Closed regular languages

Are regular languages closed under the following construction? $f(L) = \{w \mid w \in L$ and for all prefixes $x$ of $w$ it holds that $x \notin L$ $\}$
422 views

### How to convert this NFA to DFA?

What are the steps for converting this NFA to a DFA??
88 views

### Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^*$: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
133 views

### Is there a prefix-free regular language whose set of proper prefixes is not regular

Is there a regular language $L$ such that the language $$L^\prime := \{ w : w\text{ is a proper prefix of a word in }L \}$$ has the following properties: $L^\prime$ is not regular, and $L^\prime$ ...
32 views

### Subset of regular languages

Assume $L_1$ and $L_2$ two regular languages, and $L_1\subseteq L\subseteq L_2$. Does this imply that $L$ is a regular language? Thanks in advance.
103 views

### Determine the language that corresponds to the following automata.

I want to determine that language that corresponds to the following automata Note: $q_{6}$ have arrow to $a$ to himself. I started with the minimal words: $aaabb$ $aaba$ $aaaba$ $bababa$ the ...
3k views

1k views

### Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
232 views

### Prove or disprove whether the following is a regular language

I'm given the regular language L, and w being an element of L. If we remove the w from the language L, will the resulting language be still regular? Well I thought to be true. Since initially is a ...
40 views

### Eliminating Unit Productions

Eliminate all unit-productions from the grammar: $S \rightarrow abA\:|\:A\:|\:B$ $A \rightarrow B\:|\:ba\:|\:aBA$ $B \rightarrow A\:|\:aa\:|\:aA$ An article I was reading said that a unit ...
36 views

### Are these two languages equivalent?

$L = \{w \in \{a,b\}^{*}$ such that $w = R(w)\}$ R(w) = the reverse of w $L = \{u \in \{a,b\}^{*}\}$ If not can you draw a pda or define a grammar for each? I don't see how they could have ...