# Tagged Questions

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

1answer
58 views

### Intersection of context-free language and its reversal

I know that intersection of two context-free languages is not always context-free and the following problem: Given two context-free languages A and B, is $A \bigcap B \neq \emptyset$ ? is ...
1answer
57 views

### Closure properties between 2 languages of different types

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
1answer
42 views

0answers
339 views

### Help with proving a language is regular (Sipser problem 1.49a)

I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated. This question is ...
2answers
246 views

### Divisibility problem using DFA

Original problem: Create a DFA for every positive integer $k$, so that when DFA takes a binary string (reading from most significant bit), decides whether the number is divisible by $k$. A DFA for a ...
0answers
74 views

### Pumping Lemma for Context Free Languages: Is this language CFL?

I am learning for the first time the Pumping Lemma for CFL, and I thought I understood how it works until I came across this example: "Show that $L = \{a^m b^m c^n \mid m \leq n\}$ is not a CFL." My ...
1answer
58 views

### Turing machine that goes left on first symbol

I have a turing machine with transitions given by the following table I'm inputting the string aaaa. So if I look at the first symbol "a" in state A, it says to replace it with an X, go into state ...
1answer
68 views

### How to prove that a language L is not a regular language?

Given the following question: Prove that the following language is not a regular language: A language L in alphabet $\Sigma = \{a, b\}$ where every word $w$...
2answers
197 views

### State diagram of DFA

I'm trying to understand how to create state diagram of DFA. I found following example. On the first diagram I dont understand why we need fourth state when third state is final and there is no ...
0answers
48 views

### how to create transition system/automata for modulo 4

I don't know how to think when to build a transition system/automata to calculate modulo 4 a of binary numbers. I know that the last two binary digits gives the rest but I need to go through hole ...
1answer
1k views

### Create DFA that accept language where number of 0's is even and after every 1 goes 0

Alphabet ${} = \{0,1\}$. Language $L = \{ w \in \{0,1\}^* \mid \text{ number of$0$'s in$w$is even and after every$1$goes$0$} \}$. I'm trying to create DFA that accepts language $L$. But I ...
0answers
42 views

### Size of automata or regular expressions avoiding cross patterns

Let $\Sigma$ be an alphabet of finite size $k$, and $n$ some integer. I am interested in the language of words of size $n$ that do not contain $abab$ as a subword, for any pair $(a,b) \in \Sigma$ (I ...
1answer
67 views

1answer
307 views

### Constructing a NFA from a right linear grammar, is this correct?

Given the right linear grammar G S -> abA | bbB | a A -> bB | aA | b B -> baB | aaaA | [Epsilon/Terminates] Is the NFA in the image below the proper ...
1answer
188 views

### Difference between a*b and a*+b? Does the “+” denote Kleene plus or “or”?

Me and a friend are study for a quiz and are trying to determine the difference between the two NFA's produce by the regular exressions a*b and ...